File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Non-shared edges and nearest neighbor interchanges revisited
  • 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
2013 Impact Factor: 0.479
2013 SCImago Journal Rankings: 0.738
 
DOIhttp://dx.doi.org/10.1016/j.ipl.2004.04.003
 
ISI Accession Number IDWOS:000222536100004
 
ReferencesReferences in Scopus
 
DC FieldValue
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
2013 Impact Factor: 0.479
2013 SCImago Journal Rankings: 0.738
 
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
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Hon, WK</contributor.author>
<contributor.author>Kao, MY</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2010-09-06T09:50:17Z</date.accessioned>
<date.available>2010-09-06T09:50:17Z</date.available>
<date.issued>2004</date.issued>
<identifier.citation>Information Processing Letters, 2004, v. 91 n. 3, p. 129-134</identifier.citation>
<identifier.issn>0020-0190</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/88931</identifier.uri>
<description.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. &#169; 2004 Elsevier B.V. All rights reserved.</description.abstract>
<language>eng</language>
<publisher>Elsevier BV. The Journal&apos;s web site is located at http://www.elsevier.com/locate/ipl</publisher>
<relation.ispartof>Information Processing Letters</relation.ispartof>
<rights>Information Processing Letters. Copyright &#169; Elsevier BV.</rights>
<subject>Algorithms</subject>
<subject>NNI distance</subject>
<subject>Non-shared edge distance</subject>
<subject>Phylogenetic tree</subject>
<title>Non-shared edges and nearest neighbor interchanges revisited</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0020-0190&amp;volume=91&amp;issue=3&amp;spage=129&amp;epage=134&amp;date=2004&amp;atitle=Non-shared+edges+and+nearest+neighbor+interchanges+revisited</identifier.openurl>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1016/j.ipl.2004.04.003</identifier.doi>
<identifier.scopus>eid_2-s2.0-2942665985</identifier.scopus>
<identifier.hkuros>91560</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-2942665985&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>91</identifier.volume>
<identifier.issue>3</identifier.issue>
<identifier.spage>129</identifier.spage>
<identifier.epage>134</identifier.epage>
<identifier.isi>WOS:000222536100004</identifier.isi>
<publisher.place>Netherlands</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Northwestern University
  3. National University of Singapore