| Pathgroups, a dynamic data structure for genome reconstruction problems. | |
| | |
MedLine Citation:
|
PMID: 20483815 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
MOTIVATION: Ancestral gene order reconstruction problems, including the median problem, quartet construction, small phylogeny, guided genome halving and genome aliquoting, are NP hard. Available heuristics dedicated to each of these problems are computationally costly for even small instances. RESULTS: We present a data structure enabling rapid heuristic solution to all these ancestral genome reconstruction problems. A generic greedy algorithm with look-ahead based on an automatically generated priority system suffices for all the problems using this data structure. The efficiency of the algorithm is due to fast updating of the structure during run time and to the simplicity of the priority scheme. We illustrate with the first rapid algorithm for quartet construction and apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny. AVAILABILITY: http://albuquerque.bioinformatics.uottawa.ca/pathgroup/Quartet.html CONTACT: chunfang313@gmail.com SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. |
| | |
Authors:
|
Chunfang Zheng |
Related Documents
:
|
8452895 - Solvability of the electrocardiology inverse problem for a moving dipole. 20423575 - Comparison of face-to-face and telephone consultations in primary care: qualitative ana... 20809485 - Accuracy and cut-off point selection in three-class classification problems using a gen... 9711555 - Functional assays for analysis of yeast ste6 mutants. 17346495 - Removal of a non-communicating horn may not affect persistence or recurrence of endomet... 10686675 - First record of emetha audouini, a cymothoid isopod parasite, from cultured sea bass di... |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't Date: 2010-05-18 |
Journal Detail:
|
Title: Bioinformatics (Oxford, England) Volume: 26 ISSN: 1367-4811 ISO Abbreviation: Bioinformatics Publication Date: 2010 Jul |
Date Detail:
|
Created Date: 2010-06-18 Completed Date: 2010-08-26 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9808944 Medline TA: Bioinformatics Country: England |
Other Details:
|
Languages: eng Pagination: 1587-94 Citation Subset: IM |
Affiliation:
|
Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada. chunfang313@gmail.com |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Computational Biology / methods* Gene Order* Genome, Fungal Phylogeny Saccharomyces cerevisiae / genetics Yeasts / genetics* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Prediction of protein-RNA binding sites by a random forest method with combined features.
Next Document: A new data mining approach for profiling and categorizing kinetic patterns of metabolic biomarkers a...