Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem

Algorithms

Guillermo M. Mallén-Fullerton¹  J. Emilio Quiroz-Ibarra⁴  Antonio Miranda²  Guillermo Fernández-Anaya²  Giuseppe Lancia³ 

[1] Engineering Department, Universidad Iberoamericana Ciudad de México, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, Mexico; E-Mail:Physics and Mathematics Department, Universidad Iberoamericana Ciudad de México, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, Mexico;;Engineering Department, Universidad Iberoamericana Ciudad de México, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, Mexico; E-Mail;Universidad Iberoamericana Ciudad de México, DCI, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, Mexico; E-Mail:

关键词: DNA fragment assembly;    minimum spanning tree;    heap;    linear complexity;   

DOI  :  10.3390/a8030754

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY   
© 2015 by the authors; licensee MDPI, Basel, Switzerland.