Fast Algorithm for Calculating Quartet Distance Between Trees
Author Information
Author(s): Christiansen Chris, Mailund Thomas, Pedersen Christian NS, Randers Martin, Stissing Martin Stig
Primary Institution: Department of Computer Science, University of Aarhus
Hypothesis
Can we develop a faster algorithm for computing the quartet distance between trees of arbitrary degree?
Conclusion
The new algorithm significantly improves the running time for computing the quartet distance compared to previous methods.
Supporting Evidence
- The new algorithm improves the asymptotic running time for computing the quartet distance.
- Experimental results indicate that the new method performs significantly better in practice.
- The algorithm is designed to work on trees of arbitrary degree.
Takeaway
This study introduces a new way to quickly compare trees by counting how many groups of four species are arranged differently in two trees.
Methodology
The algorithm runs in time O(n + |V|·|V'| min{id, id'}) and space O(n + |V|·|V'|), where n is the number of leaves in the trees.
Limitations
The algorithm's performance may vary based on the structure of the trees being compared.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website