Graph algorithms for DNA sequencing -- origins, current models and the future

DOI10.1016/j.ejor.2016.06.043zbMath1375.92041OpenAlexW2469251889WikidataQ57387679 ScholiaQ57387679MaRDI QIDQ1681385

Marta Kasprzak, Michal Kierzynka, Wojciech Frohmberg, Aleksandra Swiercz, Piotr Zurkowski, Paweł T. Wojciechowski, Jacek Błażewicz

Publication date: 23 November 2017

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.06.043

zbMATH Keywords

graph algorithmsDNA de novo assemblywhole genome sequencing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Improved approaches to solve the one-to-one skewgram problem ⋮ New models and algorithms for RNA pseudoknot order assignment

Uses Software

• ALLPATHS
• GAGE
• Velvet
• SOAPdenovo
• CUDASW++
• G-DNA
• Bowtie 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hyper-heuristic approach to sequencing by hybridization of DNA sequences
• Sequencing by hybridization with isothermic oligonucleotide libraries
• DNA sequence assembly involving an acyclic graph model
• Finding Hamiltonian circuits in quasi-adjoint graphs
• On the recognition of de Bruijn graphs and their induced subgraphs
• Complexity of DNA sequencing by hybridization.
• Recognizing DNA graphs is difficult.
• On some properties of DNA graphs
• Embedding on alphabet overlap digraphs
• Characterizations for some types of DNA graphs
• A characterization of partial directed line graphs
• The adjoints of DNA graphs
• Computational complexity of isothermic DNA sequencing by hybridization
• Mathematical programming strategies for solving the minimum common string partition problem
• Reduced-by-matching Graphs: Toward Simplifying Hamiltonian Circuit Problem
• DNA Sequencing by Hybridization via Genetic Search
• An Eulerian path approach to DNA fragment assembly

This page was built for publication: Graph algorithms for DNA sequencing -- origins, current models and the future