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...

Descripción completa

Detalles Bibliográficos
Autores principales: Zheng, Chunfang, Sankoff, David
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