File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Phylogenetic tree reconstruction with protein linkage

TitlePhylogenetic tree reconstruction with protein linkage
Authors
KeywordsProtein Linkage
Phylogenetic Tree Reconstruction
NP-Complete
Issue Date2012
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 8th International Symposium on Bioinformatics Research and Applications (ISBRA 2012), Dallas, TX., 21-23 May 2012. In Lecture Notes in Computer Science, 2012, v. 7292, p. 315-327 How to Cite?
AbstractWhen reconstructing a phylogenetic tree, one common representation for a species is a binary string indicating the existence of some selected genes/proteins. Up until now, all existing methods have assumed the existence of these genes/proteins to be independent. However, in most cases, this assumption is not valid. In this paper, we consider the reconstruction problem by taking into account the dependency of proteins, i.e. protein linkage. We assume that the tree structure and leaf sequences are given, so we need only to find an optimal assignment to the ancestral nodes. We prove that the Phylogenetic Tree Reconstruction with Protein Linkage (PTRPL) problem for three different versions of linkage distance is NP-complete. We provide an efficient dynamic programming algorithm to solve the general problem in O(4 m •n)4 and O(4 m •(m + n)) time (compared to the straight-forward O(4 m •m •n) and O(4 m •m 2 •n) time algorithm), depending on the versions of linkage distance used, where .. stands for the number of species and .. for the number of proteins, i.e. length of binary string. We also argue, by experiments, that trees with higher accuracy can be constructed by using linkage information than by using only hamming distance to measure the differences between the binary strings, thus validating the significance of linkage information. © 2012 Springer-Verlag.
DescriptionLNCS v. 7292 is Proceedings of the 8th International Symposium on Bioinformatics Research and Applications, ISBRA 2012
Persistent Identifierhttp://hdl.handle.net/10722/152044
ISBN
ISSN
2014 SCImago Journal Rankings: 0.339
References

 

DC FieldValueLanguage
dc.contributor.authorYu, Jen_US
dc.contributor.authorLeung, HCMen_US
dc.contributor.authorYiu, SMen_US
dc.contributor.authorZhang, Yen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorHobbs, Nen_US
dc.contributor.authorWang, AYXen_US
dc.date.accessioned2012-06-26T06:32:50Z-
dc.date.available2012-06-26T06:32:50Z-
dc.date.issued2012en_US
dc.identifier.citationThe 8th International Symposium on Bioinformatics Research and Applications (ISBRA 2012), Dallas, TX., 21-23 May 2012. In Lecture Notes in Computer Science, 2012, v. 7292, p. 315-327en_US
dc.identifier.isbn978-364230190-2-
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/152044-
dc.descriptionLNCS v. 7292 is Proceedings of the 8th International Symposium on Bioinformatics Research and Applications, ISBRA 2012-
dc.description.abstractWhen reconstructing a phylogenetic tree, one common representation for a species is a binary string indicating the existence of some selected genes/proteins. Up until now, all existing methods have assumed the existence of these genes/proteins to be independent. However, in most cases, this assumption is not valid. In this paper, we consider the reconstruction problem by taking into account the dependency of proteins, i.e. protein linkage. We assume that the tree structure and leaf sequences are given, so we need only to find an optimal assignment to the ancestral nodes. We prove that the Phylogenetic Tree Reconstruction with Protein Linkage (PTRPL) problem for three different versions of linkage distance is NP-complete. We provide an efficient dynamic programming algorithm to solve the general problem in O(4 m •n)4 and O(4 m •(m + n)) time (compared to the straight-forward O(4 m •m •n) and O(4 m •m 2 •n) time algorithm), depending on the versions of linkage distance used, where .. stands for the number of species and .. for the number of proteins, i.e. length of binary string. We also argue, by experiments, that trees with higher accuracy can be constructed by using linkage information than by using only hamming distance to measure the differences between the binary strings, thus validating the significance of linkage information. © 2012 Springer-Verlag.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectProtein Linkageen_US
dc.subjectPhylogenetic Tree Reconstructionen_US
dc.subjectNP-Completeen_US
dc.titlePhylogenetic tree reconstruction with protein linkageen_US
dc.typeConference_Paperen_US
dc.identifier.emailYu, J: jjyu@cs.hku.hken_US
dc.identifier.emailLeung, HCM: cmleung2@cs.hku.hken_US
dc.identifier.emailYiu, SM: smyiu@cs.hku.hken_US
dc.identifier.emailZhang, Y: yongzh@hkucc.hku.hk-
dc.identifier.emailChin, FYL: chin@cs.hku.hk-
dc.identifier.authorityLeung, HCM=rp00144en_US
dc.identifier.authorityYiu, SM=rp00207en_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-30191-9_29en_US
dc.identifier.scopuseid_2-s2.0-84861126176en_US
dc.identifier.hkuros208036-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84861126176&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume7292en_US
dc.identifier.spage315en_US
dc.identifier.epage327en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridWang, AYX=55220601200en_US
dc.identifier.scopusauthoridHobbs, N=55216353900en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridZhang, Y=7601329213en_US
dc.identifier.scopusauthoridYiu, SM=7003282240en_US
dc.identifier.scopusauthoridLeung, HCM=35233742700en_US
dc.identifier.scopusauthoridYu, J=55219956300en_US
dc.customcontrol.immutablesml 130925-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats