Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem
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 hea...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2015-09-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/8/3/754 |
| _version_ | 1818882909027696640 |
|---|---|
| author | Guillermo M. Mallén-Fullerton J. Emilio Quiroz-Ibarra Antonio Miranda Guillermo Fernández-Anaya |
| author_facet | Guillermo M. Mallén-Fullerton J. Emilio Quiroz-Ibarra Antonio Miranda Guillermo Fernández-Anaya |
| author_sort | Guillermo M. Mallén-Fullerton |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-19T15:25:14Z |
| format | Article |
| id | doaj.art-2fb3977fa46242bda223fbbd45e1bae3 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-19T15:25:14Z |
| publishDate | 2015-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-2fb3977fa46242bda223fbbd45e1bae32022-12-21T20:15:53ZengMDPI AGAlgorithms1999-48932015-09-018375477310.3390/a8030754a8030754Modified Classical Graph Algorithms for the DNA Fragment Assembly ProblemGuillermo M. Mallén-Fullerton0J. Emilio Quiroz-Ibarra1Antonio Miranda2Guillermo Fernández-Anaya3Engineering Department, Universidad Iberoamericana Ciudad de México, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, MexicoUniversidad Iberoamericana Ciudad de México, DCI, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, MexicoPhysics and Mathematics Department, Universidad Iberoamericana Ciudad de México, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, MexicoPhysics and Mathematics Department, Universidad Iberoamericana Ciudad de México, Prolongación Paseo de la Reforma 880, Lomas de Santa Fe, Distrito Federal 01219, MexicoDNA 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.http://www.mdpi.com/1999-4893/8/3/754DNA fragment assemblyminimum spanning treeheaplinear complexity |
| spellingShingle | Guillermo M. Mallén-Fullerton J. Emilio Quiroz-Ibarra Antonio Miranda Guillermo Fernández-Anaya Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem Algorithms DNA fragment assembly minimum spanning tree heap linear complexity |
| title | Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem |
| title_full | Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem |
| title_fullStr | Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem |
| title_full_unstemmed | Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem |
| title_short | Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem |
| title_sort | modified classical graph algorithms for the dna fragment assembly problem |
| topic | DNA fragment assembly minimum spanning tree heap linear complexity |
| url | http://www.mdpi.com/1999-4893/8/3/754 |
| work_keys_str_mv | AT guillermommallenfullerton modifiedclassicalgraphalgorithmsforthednafragmentassemblyproblem AT jemilioquirozibarra modifiedclassicalgraphalgorithmsforthednafragmentassemblyproblem AT antoniomiranda modifiedclassicalgraphalgorithmsforthednafragmentassemblyproblem AT guillermofernandezanaya modifiedclassicalgraphalgorithmsforthednafragmentassemblyproblem |