Rapidly computing the phylogenetic transfer index

Jakub Truszkowski 1 Olivier Gascuel 2, 1 Krister Swenson 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given trees T and To on the same taxon set, the transfer index φ(b,To) is the number of taxa that need to be ignored so that the bipartition induced by branch b in T is equal to some bipartition in To. Recently, Lemoine et al. [13] used the transfer index to design a novel bootstrap analysis technique that improves on Felsenstein’s bootstrap on large, noisy data sets. In this work, we propose an algorithm that computes the transfer index for all branches b ∈ T in O(n log3 n) time, which improves upon the current O(n2)-time algorithm by Lin, Rajan and Moret [14]. Our implementation is able to process pairs of trees with hundreds of thousands of taxa in minutes and considerably speeds up the method of Lemoine et al. on large data sets. We believe our algorithm can be useful for comparing large phylogenies, especially when some taxa are misplaced (e.g. due to horizontal gene transfer, recombination, or reconstruction errors).
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410461
Contributor : Krister Swenson <>
Submitted on : Friday, December 13, 2019 - 6:51:05 PM
Last modification on : Monday, January 13, 2020 - 5:08:18 PM

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Jakub Truszkowski, Olivier Gascuel, Krister Swenson. Rapidly computing the phylogenetic transfer index. 19th International Workshop on Algorithms in Bioinformatics (WABI), Sep 2019, Niagara Falls, NY, United States. pp.20:1--20:12, ⟨10.4230/LIPIcs.WABI.2019.20⟩. ⟨lirmm-02410461⟩

Share

Metrics

Record views

7

Files downloads

9