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
Externally publishedYes

Fingerprint

biogeography
Identification Problem
Linear-time Algorithm
Formalization
Efficient Algorithms
NP-complete problem
Binary
Metric

Keywords

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

ASJC Scopus subject areas

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

Cite this

Pattern identification in biogeography. / Ganapathy, Ganeshkumar; Goodson, Barbara; Jansen, Robert; Le, Hai Son; Ramachandran, Vijaya; Warnow, Tandy.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 3, No. 4, 01.10.2006, p. 334-346.

Research output: Contribution to journalArticle

Ganapathy, G, Goodson, B, Jansen, R, Le, HS, Ramachandran, V & Warnow, T 2006, 'Pattern identification in biogeography', IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 3, no. 4, pp. 334-346. https://doi.org/10.1109/TCBB.2006.57
Ganapathy, Ganeshkumar ; Goodson, Barbara ; Jansen, Robert ; Le, Hai Son ; Ramachandran, Vijaya ; Warnow, Tandy. / Pattern identification in biogeography. In: IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2006 ; Vol. 3, No. 4. pp. 334-346.
@article{48258dff04dd441bb81931e230efd222,
title = "Pattern identification in biogeography",
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.",
keywords = "Area cladograms, Biogeography, Distance metrics, Maximum agreement area cladogram, Maximum agreement subset",
author = "Ganeshkumar Ganapathy and Barbara Goodson and Robert Jansen and Le, {Hai Son} and Vijaya Ramachandran and Tandy Warnow",
year = "2006",
month = "10",
day = "1",
doi = "10.1109/TCBB.2006.57",
language = "English (US)",
volume = "3",
pages = "334--346",
journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",
issn = "1545-5963",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

TY - JOUR

T1 - Pattern identification in biogeography

AU - Ganapathy, Ganeshkumar

AU - Goodson, Barbara

AU - Jansen, Robert

AU - Le, Hai Son

AU - Ramachandran, Vijaya

AU - Warnow, Tandy

PY - 2006/10/1

Y1 - 2006/10/1

N2 - 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.

AB - 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.

KW - Area cladograms

KW - Biogeography

KW - Distance metrics

KW - Maximum agreement area cladogram

KW - Maximum agreement subset

UR - http://www.scopus.com/inward/record.url?scp=33845669811&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33845669811&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2006.57

DO - 10.1109/TCBB.2006.57

M3 - Article

C2 - 17085843

AN - SCOPUS:33845669811

VL - 3

SP - 334

EP - 346

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

SN - 1545-5963

IS - 4

ER -