Pattern identification in biogeography

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

doi:10.1007/11557067_10

Pattern identification in biogeography

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	116-127
Number of pages	12
DOIs	https://doi.org/10.1007/11557067_10
State	Published - 2005
Externally published	Yes
Event	5th International Workshop on Algorithms in Bioinformatics, WABI 2005 - Mallorca, Spain Duration: Oct 3 2005 → Oct 6 2005

Publication series

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

Other

Other	5th International Workshop on Algorithms in Bioinformatics, WABI 2005
Country/Territory	Spain
City	Mallorca
Period	10/3/05 → 10/6/05

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/11557067_10

Library availability

Discover UIUC Full Text

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

Pattern identification in biogeography. / Ganapathy, Ganeshkumar; Goodson, Barbara; Jansen, Robert et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. p. 116-127 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3692 LNBI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3692 LNBI, pp. 116-127, 5th International Workshop on Algorithms in Bioinformatics, WABI 2005, Mallorca, Spain, 10/3/05. https://doi.org/10.1007/11557067_10

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

Ganapathy, Ganeshkumar ; Goodson, Barbara ; Jansen, Robert et al. / Pattern identification in biogeography. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. pp. 116-127 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ace976fac9054b11b9c1f4529da0ed11,

title = "Pattern identification in biogeography",

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.",

author = "Ganeshkumar Ganapathy and Barbara Goodson and Robert Jansen and Vijaya Ramachandran and Tandy Warnow",

year = "2005",

doi = "10.1007/11557067_10",

language = "English (US)",

isbn = "3540290087",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "116--127",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "5th International Workshop on Algorithms in Bioinformatics, WABI 2005 ; Conference date: 03-10-2005 Through 06-10-2005",

}

TY - GEN

T1 - Pattern identification in biogeography

AU - Ganapathy, Ganeshkumar

AU - Goodson, Barbara

AU - Jansen, Robert

AU - Ramachandran, Vijaya

AU - Warnow, Tandy

PY - 2005

Y1 - 2005

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

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

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

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

U2 - 10.1007/11557067_10

DO - 10.1007/11557067_10

M3 - Conference contribution

AN - SCOPUS:33646180443

SN - 3540290087

SN - 9783540290087

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 116

EP - 127

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 5th International Workshop on Algorithms in Bioinformatics, WABI 2005

Y2 - 3 October 2005 through 6 October 2005

ER -

Pattern identification in biogeography

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this