File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Phylogenetic tree reconstruction with protein linkage
  • Basic View
  • Metadata View
  • XML View
TitlePhylogenetic tree reconstruction with protein linkage
 
AuthorsYu, J1
Leung, HCM1
Yiu, SM1
Zhang, Y1
Chin, FYL1
Hobbs, N2
Wang, AYX2
 
KeywordsProtein Linkage
Phylogenetic Tree Reconstruction
NP-Complete
 
Issue Date2012
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
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-327 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-30191-9_29
 
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
 
ISBN978-364230190-2
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-30191-9_29
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorYu, J
 
dc.contributor.authorLeung, HCM
 
dc.contributor.authorYiu, SM
 
dc.contributor.authorZhang, Y
 
dc.contributor.authorChin, FYL
 
dc.contributor.authorHobbs, N
 
dc.contributor.authorWang, AYX
 
dc.date.accessioned2012-06-26T06:32:50Z
 
dc.date.available2012-06-26T06:32:50Z
 
dc.date.issued2012
 
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.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.descriptionLNCS v. 7292 is Proceedings of the 8th International Symposium on Bioinformatics Research and Applications, ISBRA 2012
 
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-327 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-30191-9_29
 
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-30191-9_29
 
dc.identifier.epage327
 
dc.identifier.hkuros208036
 
dc.identifier.isbn978-364230190-2
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-84861126176
 
dc.identifier.spage315
 
dc.identifier.urihttp://hdl.handle.net/10722/152044
 
dc.identifier.volume7292
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.subjectProtein Linkage
 
dc.subjectPhylogenetic Tree Reconstruction
 
dc.subjectNP-Complete
 
dc.titlePhylogenetic tree reconstruction with protein linkage
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Yu, J</contributor.author>
<contributor.author>Leung, HCM</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<contributor.author>Zhang, Y</contributor.author>
<contributor.author>Chin, FYL</contributor.author>
<contributor.author>Hobbs, N</contributor.author>
<contributor.author>Wang, AYX</contributor.author>
<date.accessioned>2012-06-26T06:32:50Z</date.accessioned>
<date.available>2012-06-26T06:32:50Z</date.available>
<date.issued>2012</date.issued>
<identifier.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</identifier.citation>
<identifier.isbn>978-364230190-2</identifier.isbn>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/152044</identifier.uri>
<description>LNCS v. 7292 is Proceedings of the 8th International Symposium on Bioinformatics Research and Applications, ISBRA 2012</description>
<description.abstract>When 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 &#8226;n)4 and O(4 m &#8226;(m + n)) time (compared to the straight-forward O(4 m &#8226;m &#8226;n) and O(4 m &#8226;m 2 &#8226;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. &#169; 2012 Springer-Verlag.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<subject>Protein Linkage</subject>
<subject>Phylogenetic Tree Reconstruction</subject>
<subject>NP-Complete</subject>
<title>Phylogenetic tree reconstruction with protein linkage</title>
<type>Conference_Paper</type>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/978-3-642-30191-9_29</identifier.doi>
<identifier.scopus>eid_2-s2.0-84861126176</identifier.scopus>
<identifier.hkuros>208036</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-84861126176&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>7292</identifier.volume>
<identifier.spage>315</identifier.spage>
<identifier.epage>327</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Tsinghua University