File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Reconstructing an ultrametric galled phylogenetic network from a distance matrix

TitleReconstructing an ultrametric galled phylogenetic network from a distance matrix
Authors
Issue Date2006
PublisherImperial College Press. The Journal's web site is located at http://www.worldscinet.com/jbcb/jbcb.shtml
Citation
Journal Of Bioinformatics And Computational Biology, 2006, v. 4 n. 4, p. 807-832 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. © 2006 Imperial College Press.
Persistent Identifierhttp://hdl.handle.net/10722/152346
ISSN
2015 Impact Factor: 0.785
2015 SCImago Journal Rankings: 0.525
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorJansson, Jen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorYiu, SMen_US
dc.date.accessioned2012-06-26T06:37:21Z-
dc.date.available2012-06-26T06:37:21Z-
dc.date.issued2006en_US
dc.identifier.citationJournal Of Bioinformatics And Computational Biology, 2006, v. 4 n. 4, p. 807-832en_US
dc.identifier.issn0219-7200en_US
dc.identifier.urihttp://hdl.handle.net/10722/152346-
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. © 2006 Imperial College Press.en_US
dc.languageengen_US
dc.publisherImperial College Press. The Journal's web site is located at http://www.worldscinet.com/jbcb/jbcb.shtmlen_US
dc.relation.ispartofJournal of Bioinformatics and Computational Biologyen_US
dc.subject.meshAlgorithmsen_US
dc.subject.meshBiological Evolutionen_US
dc.subject.meshChromosome Mapping - Methodsen_US
dc.subject.meshComputer Simulationen_US
dc.subject.meshEvolution, Molecularen_US
dc.subject.meshModels, Geneticen_US
dc.subject.meshPhylogenyen_US
dc.subject.meshQuantitative Trait Loci - Geneticsen_US
dc.subject.meshSequence Analysis, Dna - Methodsen_US
dc.titleReconstructing an ultrametric galled phylogenetic network from a distance matrixen_US
dc.typeArticleen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityYiu, SM=rp00207en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1142/S0219720006002211en_US
dc.identifier.pmid17007069-
dc.identifier.scopuseid_2-s2.0-33750453742en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33750453742&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume4en_US
dc.identifier.issue4en_US
dc.identifier.spage807en_US
dc.identifier.epage832en_US
dc.publisher.placeUnited Kingdomen_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridJansson, J=10439175200en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridYiu, SM=7003282240en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats