A Quadratic Time Algorithm for Computing the Quartet Distance between Two General Trees

Thomas Mailund, Jesper Nielsen, Christian Storm Pedersen

    Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

    Abstract

    We derive a quadratic time and space algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degreeges3. The time and space complexity of our algorithm is quadratic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm for computing the quartet distance between general trees independent of the degree of the inner nodes.
    OriginalsprogEngelsk
    TitelProceedings of IJCBS 2009
    Antal sider4
    ForlagIEEE Computer Society Press
    Publikationsdato2009
    Sider565-568
    ISBN (Trykt)978-0-7695-3739-9
    DOI
    StatusUdgivet - 2009
    BegivenhedInternational Joint Conferences on Bioinformatics, Systems Biology and Intelligent Computing (IJCBS) - Shanghai, Kina
    Varighed: 3 aug. 20095 aug. 2009

    Konference

    KonferenceInternational Joint Conferences on Bioinformatics, Systems Biology and Intelligent Computing (IJCBS)
    Land/OmrådeKina
    ByShanghai
    Periode03/08/200905/08/2009

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'A Quadratic Time Algorithm for Computing the Quartet Distance between Two General Trees'. Sammen danner de et unikt fingeraftryk.

    Citationsformater