Pattern identification in biogeography

Ganeshkumar Ganapathy, Barbara Goodson, Robert Jansen, Hai Son Le, Vijaya Ramachandran, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

Identifying common patterns among area cladograms that arise in historical biogeography is an important tool for biogeographical inference. We develop the first rigorous formalization of these pattern-identification problems. We develop metrics to compare area cladograms. We define the maximum agreement area cladogram (MAAC) and we develop efficient algorithms for finding the MAAC of two area cladograms, while showing that it is NP-hard to find the MAAC of several binary area cladograms. We also describe a linear-time algorithm to identify if two area cladograms are identical.

Original languageEnglish (US)
Pages (from-to)334-346
Number of pages13
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume3
Issue number4
DOIs
StatePublished - Oct 1 2006

Keywords

  • Area cladograms
  • Biogeography
  • Distance metrics
  • Maximum agreement area cladogram
  • Maximum agreement subset

ASJC Scopus subject areas

  • Engineering(all)
  • Agricultural and Biological Sciences (miscellaneous)

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

  • Cite this