Pattern identification in biogeography

Ganeshkumar Ganapathy, Barbara Goodson, Robert Jansen, Vijaya Ramachandran, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We develop and study two distance metrics for area cladograms (leaf-labeled trees where many leaves can share the same label): the edge contract and- refine metric and the MAAC distance metric. We demonstrate that in contrast to phylogenies, the contract-and-refine distance between two area cladograms is not identical to the character encoding distance, and the latter is not a metric. We present a polynomial time algorithm to compute the MAAC distance, based on a polynomial-time algorithm for computing the largest common pruned subtree of two area cladograms. We also describe a linear time algorithm to decide if two area cladograms are identical.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages116-127
Number of pages12
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event5th International Workshop on Algorithms in Bioinformatics, WABI 2005 - Mallorca, Spain
Duration: Oct 3 2005Oct 6 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3692 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Workshop on Algorithms in Bioinformatics, WABI 2005
CountrySpain
CityMallorca
Period10/3/0510/6/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Pattern identification in biogeography'. Together they form a unique fingerprint.

  • Cite this

    Ganapathy, G., Goodson, B., Jansen, R., Ramachandran, V., & Warnow, T. (2005). Pattern identification in biogeography. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 116-127). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3692 LNBI). https://doi.org/10.1007/11557067_10