Cargando…
On the PATHGROUPS approach to rapid small phylogeny
We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for cho...
Autores principales: | , |
---|---|
Formato: | Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2011
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3044296/ https://www.ncbi.nlm.nih.gov/pubmed/21342571 http://dx.doi.org/10.1186/1471-2105-12-S1-S4 |
_version_ | 1782198713831129088 |
---|---|
author | Zheng, Chunfang Sankoff, David |
author_facet | Zheng, Chunfang Sankoff, David |
author_sort | Zheng, Chunfang |
collection | PubMed |
description | We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step. Since accuracy deteriorates for sets of highly divergent genomes, we investigate strategies for improving accuracy and expanding the range of data sets where accurate reconstructions can be expected. This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing. We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny. |
format | Text |
id | pubmed-3044296 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2011 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-30442962011-02-25 On the PATHGROUPS approach to rapid small phylogeny Zheng, Chunfang Sankoff, David BMC Bioinformatics Research We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step. Since accuracy deteriorates for sets of highly divergent genomes, we investigate strategies for improving accuracy and expanding the range of data sets where accurate reconstructions can be expected. This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing. We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny. BioMed Central 2011-02-15 /pmc/articles/PMC3044296/ /pubmed/21342571 http://dx.doi.org/10.1186/1471-2105-12-S1-S4 Text en Copyright ©2011 Zheng and Sankoff; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (<url>http://creativecommons.org/licenses/by/2.0</url>), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Zheng, Chunfang Sankoff, David On the PATHGROUPS approach to rapid small phylogeny |
title | On the PATHGROUPS approach to rapid small phylogeny |
title_full | On the PATHGROUPS approach to rapid small phylogeny |
title_fullStr | On the PATHGROUPS approach to rapid small phylogeny |
title_full_unstemmed | On the PATHGROUPS approach to rapid small phylogeny |
title_short | On the PATHGROUPS approach to rapid small phylogeny |
title_sort | on the pathgroups approach to rapid small phylogeny |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3044296/ https://www.ncbi.nlm.nih.gov/pubmed/21342571 http://dx.doi.org/10.1186/1471-2105-12-S1-S4 |
work_keys_str_mv | AT zhengchunfang onthepathgroupsapproachtorapidsmallphylogeny AT sankoffdavid onthepathgroupsapproachtorapidsmallphylogeny |