A sub-cubic time algorithm for computing the quartet distance between two general trees

BACKGROUND: When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure, and is the number of quartet topologies that differ between two trees. RESULTS: We have der...

Descripción completa

Detalles Bibliográficos
Autores principales: Nielsen, Jesper, Kristensen, Anders K, Mailund, Thomas, Pedersen, Christian NS
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2011
Materias:
Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3141660/
https://www.ncbi.nlm.nih.gov/pubmed/21639882
http://dx.doi.org/10.1186/1748-7188-6-15
_version_ 1782208729189449728
author Nielsen, Jesper
Kristensen, Anders K
Mailund, Thomas
Pedersen, Christian NS
author_facet Nielsen, Jesper
Kristensen, Anders K
Mailund, Thomas
Pedersen, Christian NS
author_sort Nielsen, Jesper
collection PubMed
description BACKGROUND: When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure, and is the number of quartet topologies that differ between two trees. RESULTS: We have derived a new algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degree ≥ 3. The time and space complexity of our algorithm is sub-cubic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm so far for computing the quartet distance between general trees independent of the degree of the inner nodes. CONCLUSIONS: We have implemented our algorithm and two of the best competitors. Our new algorithm is significantly faster than the competition and seems to run in close to quadratic time in practice.
format Online
Article
Text
id pubmed-3141660
institution National Center for Biotechnology Information
language English
publishDate 2011
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-31416602011-07-23 A sub-cubic time algorithm for computing the quartet distance between two general trees Nielsen, Jesper Kristensen, Anders K Mailund, Thomas Pedersen, Christian NS Algorithms Mol Biol Research BACKGROUND: When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure, and is the number of quartet topologies that differ between two trees. RESULTS: We have derived a new algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degree ≥ 3. The time and space complexity of our algorithm is sub-cubic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm so far for computing the quartet distance between general trees independent of the degree of the inner nodes. CONCLUSIONS: We have implemented our algorithm and two of the best competitors. Our new algorithm is significantly faster than the competition and seems to run in close to quadratic time in practice. BioMed Central 2011-06-03 /pmc/articles/PMC3141660/ /pubmed/21639882 http://dx.doi.org/10.1186/1748-7188-6-15 Text en Copyright ©2011 Nielsen et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research
Nielsen, Jesper
Kristensen, Anders K
Mailund, Thomas
Pedersen, Christian NS
A sub-cubic time algorithm for computing the quartet distance between two general trees
title A sub-cubic time algorithm for computing the quartet distance between two general trees
title_full A sub-cubic time algorithm for computing the quartet distance between two general trees
title_fullStr A sub-cubic time algorithm for computing the quartet distance between two general trees
title_full_unstemmed A sub-cubic time algorithm for computing the quartet distance between two general trees
title_short A sub-cubic time algorithm for computing the quartet distance between two general trees
title_sort sub-cubic time algorithm for computing the quartet distance between two general trees
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3141660/
https://www.ncbi.nlm.nih.gov/pubmed/21639882
http://dx.doi.org/10.1186/1748-7188-6-15
work_keys_str_mv AT nielsenjesper asubcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT kristensenandersk asubcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT mailundthomas asubcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT pedersenchristianns asubcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT nielsenjesper subcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT kristensenandersk subcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT mailundthomas subcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees
AT pedersenchristianns subcubictimealgorithmforcomputingthequartetdistancebetweentwogeneraltrees

Ejemplares similares