Modified classical graph algorithms for the DNA fragment assembly problem

DOI10.3390/A8030754MaRDI QIDQ1736710zbMATH OpenOpenAlexFDO

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

Publication date 26 March 2019

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/a8030754

zbMATH Keywords

DNA fragment assemblyheaplinear complexityminimum spanning tree

Mathematics Subject Classification ID

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

Review text

Summary: DNA fragment assembly represents an important challenge to the development of efficient and practical algorithms due to the large number of elements to be assembled. In this study, we present some graph theoretical linear time algorithms to solve the problem. To achieve linear time complexity, a heap with constant time operations was developed, for the special case where the edge weights are integers and do not depend on the problem size. The experiments presented show that modified classical graph theoretical algorithms can solve the DNA fragment assembly problem efficiently.

Recommendations

• DNA paired fragment assembly using graph theory
• DNA sequence assembly involving an acyclic graph model
• The contig assembly problem and its algorithmic solutions
• A Hybrid Genetic Algorithm for the DNA Fragment Assembly Problem
• Seeding strategies and recombination operators for solving the DNA fragment assembly problem

Cites work

• An Eulerian path approach to DNA fragment assembly
• DNA paired fragment assembly using graph theory
• On finding minimal length superstrings
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Set Merging Algorithms

Cited in

(7)

• DNA paired fragment assembly using graph theory
• Unimodular hypergraph for DNA sequencing: a polynomial time algorithm
• scientific article; zbMATH DE number 1301602 (Why is no real title available?)
• An Eulerian path approach to DNA fragment assembly
• Linear-time superbubble identification algorithm for genome assembly
• DNA sequence assembly involving an acyclic graph model
• Seeding strategies and recombination operators for solving the DNA fragment assembly problem

Describes a project that uses

Uses Software

• GAGE

This page was built for publication: Modified classical graph algorithms for the DNA fragment assembly problem

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