Non-shared edges and nearest neighbor interchanges revisited

Wing Kai Hon, Ming-Yang Kao, Tak Wah Lam, Wing Kin Sung*, Siu Ming Yiu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The number of non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edge distance is also a building block for approximating a more sophisticated measure called the nearest neighbor interchange (NNI) distance. In this paper, we give the first sub-quadratic time algorithm for computing the non-shared edge distance, whose running time is O(nlogn). Based on this result, we can speed up the existing approximation algorithm for the NNI distance from O(n2) time to O(nlogn) time.

Original languageEnglish (US)
Pages (from-to)129-134
Number of pages6
JournalInformation Processing Letters
Volume91
Issue number3
DOIs
StatePublished - Aug 16 2004

Funding

* Corresponding author. E-mail addresses: [email protected] (W.-K. Hon), [email protected] (M.-Y. Kao), [email protected] (T.-W. Lam), [email protected] (W.-K. Sung), [email protected] (S.-M. Yiu). 1 Supported in part by NSF grant EIA-0112934.

Keywords

  • Algorithms
  • NNI distance
  • Non-shared edge distance
  • Phylogenetic tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Non-shared edges and nearest neighbor interchanges revisited'. Together they form a unique fingerprint.

Cite this