Computing the distribution of the Robinson-Foulds distance
File(s)
Published version
Author(s)
Hayati, Maryam
Chindelevitch, Leonid
Type
Journal Article
Abstract
With the exponential growth of genome databases, the importance of phylogenetics has increased dramatically over the past years. Studying phylogenetic trees enables us not only to understand how genes, genomes, and species evolve, but also helps us predict how they might change in future. One of the crucial aspects of phylogenetics is the comparison of two or more phylogenetic trees. There are different metrics for computing the dissimilarity between a pair of trees. The Robinson-Foulds (RF) distance is one of the widely used metrics on the space of labeled trees. The distribution of the RF distance from a given tree has been studied before, but the fastest known algorithm for computing this distribution is a slow, albeit polynomial-time, O(l5) algorithm. In this paper, we modify the dynamic programming algorithm for computing the distribution of this distance for a given tree by leveraging the number-theoretic transform (NTT), and improve the running time from O(l5) to O(l3 log l), where l is the number of tips of the tree. In addition to its practical usefulness, our method represents a theoretical novelty, as it is, to our knowledge, one of the rare applications of the number-theoretic transform for solving a computational biology problem.
Date Issued
2020-08-01
Date Acceptance
2020-05-09
Citation
Computational Biology and Chemistry, 2020, 87
ISSN
1476-9271
Publisher
Elsevier
Journal / Book Title
Computational Biology and Chemistry
Volume
87
Copyright Statement
© 2020 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/BY/4.0/)
License URL
Subjects
Bioinformatics
03 Chemical Sciences
06 Biological Sciences
08 Information and Computing Sciences
Publication Status
Published
Article Number
ARTN 107284
Date Publish Online
2020-05-19