### 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 | |

State | Published - Dec 1 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 | Spain |

City | Mallorca |

Period | 10/3/05 → 10/6/05 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

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

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

*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

}

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 -