Cargando…
Improved Heuristics for Minimum-Flip Supertree Construction
The utility of the matrix representation with flipping (MRF) supertree method has been limited by the speed of its heuristic algorithms. We describe a new heuristic algorithm for MRF supertree construction that improves upon the speed of the previous heuristic by a factor of n (the number of taxa in...
Autores principales: | , , , |
---|---|
Formato: | Texto |
Lenguaje: | English |
Publicado: |
Libertas Academica
2007
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2674677/ https://www.ncbi.nlm.nih.gov/pubmed/19455229 |
_version_ | 1782166664659337216 |
---|---|
author | Chen, Duhong Eulenstein, Oliver Fernández-Baca, David Burleigh, J. Gordon |
author_facet | Chen, Duhong Eulenstein, Oliver Fernández-Baca, David Burleigh, J. Gordon |
author_sort | Chen, Duhong |
collection | PubMed |
description | The utility of the matrix representation with flipping (MRF) supertree method has been limited by the speed of its heuristic algorithms. We describe a new heuristic algorithm for MRF supertree construction that improves upon the speed of the previous heuristic by a factor of n (the number of taxa in the supertree). This new heuristic makes MRF tractable for large-scale supertree analyses and allows the first comparisons of MRF with other supertree methods using large empirical data sets. Analyses of three published supertree data sets with between 267 to 571 taxa indicate that MRF supertrees are equally or more similar to the input trees on average than matrix representation with parsimony (MRP) and modified min-cut supertrees. The results also show that large differences may exist between MRF and MRP supertrees and demonstrate that the MRF supertree method is a practical and potentially more accurate alternative to the nearly ubiquitous MRP supertree method. |
format | Text |
id | pubmed-2674677 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2007 |
publisher | Libertas Academica |
record_format | MEDLINE/PubMed |
spelling | pubmed-26746772009-05-19 Improved Heuristics for Minimum-Flip Supertree Construction Chen, Duhong Eulenstein, Oliver Fernández-Baca, David Burleigh, J. Gordon Evol Bioinform Online Original Research The utility of the matrix representation with flipping (MRF) supertree method has been limited by the speed of its heuristic algorithms. We describe a new heuristic algorithm for MRF supertree construction that improves upon the speed of the previous heuristic by a factor of n (the number of taxa in the supertree). This new heuristic makes MRF tractable for large-scale supertree analyses and allows the first comparisons of MRF with other supertree methods using large empirical data sets. Analyses of three published supertree data sets with between 267 to 571 taxa indicate that MRF supertrees are equally or more similar to the input trees on average than matrix representation with parsimony (MRP) and modified min-cut supertrees. The results also show that large differences may exist between MRF and MRP supertrees and demonstrate that the MRF supertree method is a practical and potentially more accurate alternative to the nearly ubiquitous MRP supertree method. Libertas Academica 2007-02-28 /pmc/articles/PMC2674677/ /pubmed/19455229 Text en Copyright © 2006 The authors. http://creativecommons.org/licenses/by/3.0 This article is published under the Creative Commons Attribution By licence. For further information go to: http://creativecommons.org/licenses/by/3.0. (http://creativecommons.org/licenses/by/3.0) |
spellingShingle | Original Research Chen, Duhong Eulenstein, Oliver Fernández-Baca, David Burleigh, J. Gordon Improved Heuristics for Minimum-Flip Supertree Construction |
title | Improved Heuristics for Minimum-Flip Supertree Construction |
title_full | Improved Heuristics for Minimum-Flip Supertree Construction |
title_fullStr | Improved Heuristics for Minimum-Flip Supertree Construction |
title_full_unstemmed | Improved Heuristics for Minimum-Flip Supertree Construction |
title_short | Improved Heuristics for Minimum-Flip Supertree Construction |
title_sort | improved heuristics for minimum-flip supertree construction |
topic | Original Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2674677/ https://www.ncbi.nlm.nih.gov/pubmed/19455229 |
work_keys_str_mv | AT chenduhong improvedheuristicsforminimumflipsupertreeconstruction AT eulensteinoliver improvedheuristicsforminimumflipsupertreeconstruction AT fernandezbacadavid improvedheuristicsforminimumflipsupertreeconstruction AT burleighjgordon improvedheuristicsforminimumflipsupertreeconstruction |