### Abstract

The number of the non-shared edges of two phylogenies is a basic measure of the distance (dissimilarity) between the phylogenies. The non-shared edges are also the building block for approximating a more sophisticated metric called the NNI distance. In this paper we give the first sub-quadratic time algorithm for finding the non-shared edges, which are then used to speed up the existing approximation algorithm for the NNI distance. The time is improved from O(n^{2}) to O(n log n). Another popular distance metric for phylogenies is the STT distance. Previous work on computing the STT distance focused on degree-3 trees only. We show that the STT distance can be applied in a broader sense, allowing us to cover degree-d trees, where d ≥ 3. In particular, we give a new approximation algorithm for the STT distance.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings |

Editors | Shang-Hua Teng, D.T. Lee, Shang-Hua Teng |

Publisher | Springer Verlag |

Pages | 527-538 |

Number of pages | 12 |

ISBN (Print) | 3540412557, 9783540412557 |

State | Published - Jan 1 2000 |

Event | 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China Duration: Dec 18 2000 → Dec 20 2000 |

### Publication series

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

Volume | 1969 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 |
---|---|

Country | Taiwan, Province of China |

City | Taipei |

Period | 12/18/00 → 12/20/00 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings*(pp. 527-538). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969). Springer Verlag.