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

Fingerprint

Distance Metric
Polynomials
Polynomial-time Algorithm
Leaves
Metric
Labeled Trees
Labels
Phylogeny
Linear-time Algorithm
Encoding
Computing
Demonstrate
Character

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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; Ramachandran, Vijaya; Warnow, Tandy.

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 proceedingConference 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)). https://doi.org/10.1007/11557067_10
Ganapathy, Ganeshkumar ; Goodson, Barbara ; Jansen, Robert ; Ramachandran, Vijaya ; Warnow, Tandy. / 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",
month = "12",
day = "1",
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)",

}

TY - GEN

T1 - Pattern identification in biogeography

AU - Ganapathy, Ganeshkumar

AU - Goodson, Barbara

AU - Jansen, Robert

AU - Ramachandran, Vijaya

AU - Warnow, Tandy

PY - 2005/12/1

Y1 - 2005/12/1

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)

ER -