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
    0 references
    0 references
    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

    Identifiers