File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Non-shared edges and nearest neighbor interchanges revisited

TitleNon-shared edges and nearest neighbor interchanges revisited
Authors
Hon, WKKao, MYLam, TWSung, WKYiu, SM
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
Citation
Information 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.
Persistent Identifierhttp://hdl.handle.net/10722/88931
ISSN
0020-0190
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
WOS:000222536100004
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorHon, WKen_HK
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-06T09:50:17Z-
dc.date.available2010-09-06T09:50:17Z-
dc.date.issued2004en_HK
dc.identifier.citationInformation Processing Letters, 2004, v. 91 n. 3, p. 129-134en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88931-
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.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.en_HK
dc.subjectAlgorithmsen_HK
dc.subjectNNI distanceen_HK
dc.subjectNon-shared edge distanceen_HK
dc.subjectPhylogenetic treeen_HK
dc.titleNon-shared edges and nearest neighbor interchanges revisiteden_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=91&issue=3&spage=129&epage=134&date=2004&atitle=Non-shared+edges+and+nearest+neighbor+interchanges+revisiteden_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.ipl.2004.04.003en_HK
dc.identifier.scopuseid_2-s2.0-2942665985en_HK
dc.identifier.hkuros91560en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-2942665985&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume91en_HK
dc.identifier.issue3en_HK
dc.identifier.spage129en_HK
dc.identifier.epage134en_HK
dc.identifier.isiWOS:000222536100004-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridHon, WK=7004282818en_HK
dc.identifier.scopusauthoridKao, MY=7202198147en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats