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

Thomas Mailund, Jesper Nielsen, Christian Storm Pedersen

    Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-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.
    Original languageEnglish
    Title of host publicationProceedings of IJCBS 2009
    Number of pages4
    PublisherIEEE Computer Society Press
    Publication date2009
    Pages565-568
    ISBN (Print)978-0-7695-3739-9
    DOIs
    Publication statusPublished - 2009
    EventInternational Joint Conferences on Bioinformatics, Systems Biology and Intelligent Computing (IJCBS) - Shanghai, China
    Duration: 3 Aug 20095 Aug 2009

    Conference

    ConferenceInternational Joint Conferences on Bioinformatics, Systems Biology and Intelligent Computing (IJCBS)
    Country/TerritoryChina
    CityShanghai
    Period03/08/200905/08/2009

    Fingerprint

    Dive into the research topics of 'A Quadratic Time Algorithm for Computing the Quartet Distance between Two General Trees'. Together they form a unique fingerprint.

    Cite this