File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Reconstructing an ultrametric galled phylogenetic network from a distance matrix

TitleReconstructing an ultrametric galled phylogenetic network from a distance matrix
Authors
Issue Date2005
PublisherSpringer 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 August-2 September 2005. In Lecture Notes in Computer Science, 2005, v. 3618, p. 224-235 How to Cite?
AbstractGiven a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted 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 NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it. © Springer-Verlag Berlin Heidelberg 2005.
DescriptionLNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005 ... Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/89021
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorJansson, Jen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-06T09:51:24Z-
dc.date.available2010-09-06T09:51:24Z-
dc.date.issued2005en_HK
dc.identifier.citationThe 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk, Poland, 29 August-2 September 2005. In Lecture Notes in Computer Science, 2005, v. 3618, p. 224-235en_HK
dc.identifier.isbn978-3-540-28702-5-
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89021-
dc.descriptionLNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005 ... Proceedings-
dc.description.abstractGiven a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted 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 NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe final publication is available at Springer via http://dx.doi.org/10.1007/11549345_20-
dc.titleReconstructing an ultrametric galled phylogenetic network from a distance matrixen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0219-7200&volume=4: 4&spage=807&epage=832&date=2006&atitle=Reconstructing+An+Ultrametric+Galled+Phylogenetic+Network+From+A+Distance+Matrix+en_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/11549345_20-
dc.identifier.scopuseid_2-s2.0-26844460384en_HK
dc.identifier.hkuros100157en_HK
dc.identifier.hkuros124384-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-26844460384&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3618en_HK
dc.identifier.spage224en_HK
dc.identifier.epage235en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridJansson, J=10439175200en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK
dc.customcontrol.immutablesml 151014 - merged-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats