Imperial College London
Portrait Picture

DrLeonidChindelevitch

Faculty of Medicine, School of Public Health

Lecturer in Infectious Disease Epidemiology
 
 
 
//

Contact

 

l.chindelevitch Website

 
 
//

Location

 

Sir Michael Uren HubWhite City Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Hayati:2020:10.1016/j.compbiolchem.2020.107284,
author = {Hayati, M and Chindelevitch, L},
doi = {10.1016/j.compbiolchem.2020.107284},
journal = {Computational Biology and Chemistry},
title = {Computing the distribution of the Robinson-Foulds distance},
url = {http://dx.doi.org/10.1016/j.compbiolchem.2020.107284},
volume = {87},
year = {2020}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Hayati,M
AU  - Chindelevitch,L
DO  - 10.1016/j.compbiolchem.2020.107284
PY  - 2020///
SN  - 1476-9271
TI  - Computing the distribution of the Robinson-Foulds distance
T2  - Computational Biology and Chemistry
UR  - http://dx.doi.org/10.1016/j.compbiolchem.2020.107284
UR  - http://hdl.handle.net/10044/1/86921
VL  - 87
ER  -
Download