File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/11549345_20
 Scopus: eid_2s2.026844460384
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Reconstructing an ultrametric galled phylogenetic network from a distance matrix
Title  Reconstructing an ultrametric galled phylogenetic network from a distance matrix 

Authors  
Issue Date  2005 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk, Poland, 29 August2 September 2005. In Lecture Notes in Computer Science, 2005, v. 3618, p. 224235 How to Cite? 
Abstract  Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edgeweighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NPhard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NPhard to determine whether there exists an ultrametric galled network which satisfies it. © SpringerVerlag Berlin Heidelberg 2005. 
Description  LNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005 ... Proceedings 
Persistent Identifier  http://hdl.handle.net/10722/89021 
ISBN  
ISSN  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Jansson, J  en_HK 
dc.contributor.author  Lam, TW  en_HK 
dc.contributor.author  Yiu, SM  en_HK 
dc.date.accessioned  20100906T09:51:24Z   
dc.date.available  20100906T09:51:24Z   
dc.date.issued  2005  en_HK 
dc.identifier.citation  The 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk, Poland, 29 August2 September 2005. In Lecture Notes in Computer Science, 2005, v. 3618, p. 224235  en_HK 
dc.identifier.isbn  9783540287025   
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/89021   
dc.description  LNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005 ... Proceedings   
dc.description.abstract  Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edgeweighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NPhard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NPhard to determine whether there exists an ultrametric galled network which satisfies it. © SpringerVerlag Berlin Heidelberg 2005.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science  en_HK 
dc.rights  The final publication is available at Springer via http://dx.doi.org/10.1007/11549345_20   
dc.title  Reconstructing an ultrametric galled phylogenetic network from a distance matrix  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=02197200&volume=4: 4&spage=807&epage=832&date=2006&atitle=Reconstructing+An+Ultrametric+Galled+Phylogenetic+Network+From+A+Distance+Matrix+  en_HK 
dc.identifier.email  Chan, HL:hlchan@cs.hku.hk  en_HK 
dc.identifier.email  Lam, TW:twlam@cs.hku.hk  en_HK 
dc.identifier.email  Yiu, SM:smyiu@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.identifier.authority  Lam, TW=rp00135  en_HK 
dc.identifier.authority  Yiu, SM=rp00207  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/11549345_20   
dc.identifier.scopus  eid_2s2.026844460384  en_HK 
dc.identifier.hkuros  100157  en_HK 
dc.identifier.hkuros  124384   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.026844460384&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  3618  en_HK 
dc.identifier.spage  224  en_HK 
dc.identifier.epage  235  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 
dc.identifier.scopusauthorid  Jansson, J=10439175200  en_HK 
dc.identifier.scopusauthorid  Lam, TW=7202523165  en_HK 
dc.identifier.scopusauthorid  Yiu, SM=7003282240  en_HK 
dc.customcontrol.immutable  sml 151014  merged   