File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximating the Nearest Neighbor Interchange Distance for Non-Uniform-Degree Evolutionary Trees

TitleApproximating the Nearest Neighbor Interchange Distance for Non-Uniform-Degree Evolutionary Trees
Authors
Issue Date2001
PublisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtml
Citation
International Journal of Foundations of Computer Science, 2001, v. 12 n. 4, p. 533-550 How to Cite?
AbstractThe nearest neighbor interchange (nni) distance is a classical metric for measuring the distance (dissimilarity) between evolutionary trees. It has been known that computing the nni distance is NP-complete. Existing approximation algorithms can attain an approximation ratio log n for unweighted trees and 4 log n for weighted trees; yet these algorithms are limited to degree-3 trees. This paper extends the study of nni distance to trees with non-uniform degrees. We formulate the necessary and sufficient conditions for nni transformation and devise more topology-sensitive approximation algorithms to handle trees with non-uniform degrees. The approximation ratios are respectively and for unweighted and weighted trees, where d ≥ 4 is the maximum degree of the input trees.
Persistent Identifierhttp://hdl.handle.net/10722/89009
ISSN
2015 Impact Factor: 0.467
2015 SCImago Journal Rankings: 0.394

 

DC FieldValueLanguage
dc.contributor.authorHon, WK-
dc.contributor.authorLam, TW-
dc.date.accessioned2010-09-06T09:51:15Z-
dc.date.available2010-09-06T09:51:15Z-
dc.date.issued2001-
dc.identifier.citationInternational Journal of Foundations of Computer Science, 2001, v. 12 n. 4, p. 533-550-
dc.identifier.issn0129-0541-
dc.identifier.urihttp://hdl.handle.net/10722/89009-
dc.description.abstractThe nearest neighbor interchange (nni) distance is a classical metric for measuring the distance (dissimilarity) between evolutionary trees. It has been known that computing the nni distance is NP-complete. Existing approximation algorithms can attain an approximation ratio log n for unweighted trees and 4 log n for weighted trees; yet these algorithms are limited to degree-3 trees. This paper extends the study of nni distance to trees with non-uniform degrees. We formulate the necessary and sufficient conditions for nni transformation and devise more topology-sensitive approximation algorithms to handle trees with non-uniform degrees. The approximation ratios are respectively and for unweighted and weighted trees, where d ≥ 4 is the maximum degree of the input trees.-
dc.languageeng-
dc.publisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtml-
dc.relation.ispartofInternational Journal of Foundations of Computer Science-
dc.rightsFor preprints : Preprint of an article published in [Journal, Volume, Issue, Year, Pages] [Article DOI] © [copyright World Scientific Publishing Company] [Journal URL] For postprints : Electronic version of an article published as [Journal, Volume, Issue, Year, Pages] [Article DOI] © [copyright World Scientific Publishing Company] [Journal URL] -
dc.titleApproximating the Nearest Neighbor Interchange Distance for Non-Uniform-Degree Evolutionary Trees-
dc.typeArticle-
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0129-0541&volume=12&issue=4&spage=533&epage=550&date=2001&atitle=Approximating+the+Nearest+Neighbor+Interchange+Distance+for+Non-Uniform-Degree+Evolutionary+Treesen_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135-
dc.identifier.doi10.1142/S0129054101000631-
dc.identifier.hkuros107464-
dc.identifier.volume12-
dc.identifier.issue4-
dc.identifier.spage533-
dc.identifier.epage550-
dc.publisher.placeSingapore-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats