Article: Non-shared edges and nearest neighbor interchanges revisited

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleNon-shared edges and nearest neighbor interchanges revisited
AuthorsHon, WK1
Kao, MY2
Lam, TW1
Sung, WK3
Yiu, SM1
KeywordsAlgorithms
NNI distance
Non-shared edge distance
Phylogenetic tree
Issue Date2004
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
CitationInformation Processing Letters, 2004, v. 91 n. 3, p. 129-134 [How to Cite?]
DOI: http://dx.doi.org/10.1016/j.ipl.2004.04.003
AbstractThe 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. © 2004 Elsevier B.V. All rights reserved.
ISSN0020-0190
2011 Impact Factor: 0.455
2011 SCImago Journal Rankings: 0.046
DOIhttp://dx.doi.org/10.1016/j.ipl.2004.04.003
ISI Accession Number IDWOS:000222536100004
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorHon, WK
dc.contributor.authorKao, MY
dc.contributor.authorLam, TW
dc.contributor.authorSung, WK
dc.contributor.authorYiu, SM
dc.date.accessioned2010-09-06T09:50:17Z
dc.date.available2010-09-06T09:50:17Z
dc.date.issued2004
dc.description.abstractThe 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. © 2004 Elsevier B.V. All rights reserved.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationInformation Processing Letters, 2004, v. 91 n. 3, p. 129-134 [How to Cite?]
DOI: http://dx.doi.org/10.1016/j.ipl.2004.04.003
dc.identifier.doihttp://dx.doi.org/10.1016/j.ipl.2004.04.003
dc.identifier.epage134
dc.identifier.hkuros91560
dc.identifier.isiWOS:000222536100004
dc.identifier.issn0020-0190
2011 Impact Factor: 0.455
2011 SCImago Journal Rankings: 0.046
dc.identifier.issue3
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-2942665985
dc.identifier.spage129
dc.identifier.urihttp://hdl.handle.net/10722/88931
dc.identifier.volume91
dc.languageeng
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
dc.publisher.placeNetherlands
dc.relation.ispartofInformation Processing Letters
dc.relation.referencesReferences in Scopus
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.
dc.subjectAlgorithms
dc.subjectNNI distance
dc.subjectNon-shared edge distance
dc.subjectPhylogenetic tree
dc.titleNon-shared edges and nearest neighbor interchanges revisited
dc.typeArticle
Author Affiliations
  1. The University of Hong Kong
  2. Northwestern University
  3. National University of Singapore