An efficient algorithm for the rooted triplet distance between galled trees (Q2364900)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient algorithm for the rooted triplet distance between galled trees |
scientific article |
Statements
An efficient algorithm for the rooted triplet distance between galled trees (English)
0 references
25 July 2017
0 references
The authors present a faster approach for calculating the rooted triplet distance between two galled trees (a special case of phylogenetic networks in which all underlying cycles are vertex disjoint) and thus reduce the algorithm complexity from \(O(n^{2.687})\) to \(O(n\log{n})\), with \(n\) is the number of leaves. Following an overview of existing algorithms and a formal summary of concepts, the authors present the new approach based on a transformation of the input and the method developed for counting common resolved triplets and common fan triplets. For the entire collection see [Zbl 1365.92002].
0 references
phylogenetic network comparison
0 references
galled tree
0 references
rooted triplet
0 references
algorithm
0 references
computational complexity
0 references