2002/11/11 by Wing-Kai Hon, Ming‐Yang Kao, Hon, Wing-Kai +11
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Computer Science · #Banana Cultivation and Research #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0211009
arxiv created 2002/11/11 · openalex publication_date 2002/11/11 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The number of the non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edges are also the building block for approximating a more sophisticated metric called the nearest neighbor interchange (NNI) distance. In this paper, we give the first subquadratic-time algorithm for finding the non-shared edges, which are then used to speed up the existing approximating algorithm for the NNI distance from O(n2) time to O(n log n) time. Another popular distance metric for phylogenies is the subtree transfer (STT) distance. Previous work on computing the STT distance considered degree-3 trees only. We give an approximation algorithm for the STT distance for degree-d trees with arbitrary d and with generalized STT operations.