DNA paired fragment assembly using graph theory

DOI10.3390/A10020036MaRDI QIDQ1662696zbMATH OpenOpenAlexFDO

Authors J. Emilio Quiroz-Ibarra, Guillermo M. Mallén-Fullerton, Guillermo Fernández-Anaya

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a10020036

zbMATH Keywords

DNA fragment assemblygraph theory algorithmstrie data structure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Data structures (68P05) Protein sequences, DNA sequences (92D20)

Review text

Summary: DNA fragment assembly requirements have generated an important computational problem created by their structure and the volume of data. Therefore, it is important to develop algorithms able to produce high-quality information that use computer resources efficiently. Such an algorithm, using graph theory, is introduced in the present article. We first determine the overlaps between DNA fragments, obtaining the edges of a directed graph; with this information, the next step is to construct an adjacency list with some particularities. Using the adjacency list, it is possible to obtain the DNA \textit{contigs} (group of assembled fragments building a contiguous element) using graph theory. We performed a set of experiments on real DNA data and compared our results to those obtained with common assemblers (\textit{Edena} and \textit{Velvet}). Finally, we searched the \textit{contigs} in the original genome, in our results and in those of \textit{Edena} and \textit{Velvet}.

Recommendations

• Modified classical graph algorithms for the DNA fragment assembly problem
• Applications of graph theory in DNA sequencing by hybridization
• DNA sequence assembly involving an acyclic graph model
• Graph theoretic approach to parallel gene assembly
• DNA fragment assembly using a grid-based genetic algorithm
• DNA recombination through assembly graphs
• An Eulerian path approach to DNA fragment assembly
• DNA computing of bipartite graphs for maximum matching
• scientific article; zbMATH DE number 5526120

Cites work

• Modified classical graph algorithms for the DNA fragment assembly problem
• On-line construction of suffix trees
• When the greedy algorithm fails

Cited in

(12)

• Gene assembly through cyclic graph decomposition
• Graph algorithms for DNA sequencing -- origins, current models and the future
• Modified classical graph algorithms for the DNA fragment assembly problem
• DNA fragment assembly using a grid-based genetic algorithm
• The adjoints of DNA graphs
• DNA fragments assembly programs: A comparative study
• scientific article; zbMATH DE number 2086218 (Why is no real title available?)
• scientific article; zbMATH DE number 1738644 (Why is no real title available?)
• An Eulerian path approach to DNA fragment assembly
• scientific article; zbMATH DE number 6282157 (Why is no real title available?)
• A study of computational genome assembly by graph theory
• Graph theory analysis of genomics problems: Community analysis of fragile sites correlations and of pseudogenes alignments

Describes a project that uses

Uses Software

• QUAST
• Velvet
• MUMMER
• Genomatix

This page was built for publication: DNA paired fragment assembly using graph theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662696)