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 language | English (US) |
---|---|
Pages (from-to) | 129-134 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 91 |
Issue number | 3 |
DOIs | |
State | Published - 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