Linked Life Data

16873515

Source:http://linkedlifedata.com/resource/pubmed/id/16873515

Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
14
pubmed:dateCreated
2006-7-28
pubmed:abstractText
We explore the problem of constructing near-perfect phylogenies on bi-allelic haplotypes, where the deviation from perfect phylogeny is entirely due to homoplasy events. We present polynomial-time algorithms for restricted versions of the problem. We show that these algorithms can be extended to genotype data, in which case the problem is called the near-perfect phylogeny haplotyping (NPPH) problem. We present a near-optimal algorithm for the H1-NPPH problem, which is to determine if a given set of genotypes admit a phylogeny with a single homoplasy event. The time-complexity of our algorithm for the H1-NPPH problem is O(m2(n + m)), where n is the number of genotypes and m is the number of SNP sites. This is a significant improvement over the earlier O(n4) algorithm. We also introduce generalized versions of the problem. The H(1, q)-NPPH problem is to determine if a given set of genotypes admit a phylogeny with q homoplasy events, so that all the homoplasy events occur in a single site. We present an O(m(q+1)(n + m)) algorithm for the H(1,q)-NPPH problem.
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:status
MEDLINE
pubmed:month
Jul
pubmed:issn
1367-4811
pubmed:author
pubmed:issnType
Electronic
pubmed:day
15
pubmed:volume
22
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
e514-22
pubmed:dateRevised
2010-11-18
pubmed:meshHeading
pubmed:year
2006
pubmed:articleTitle
Constructing near-perfect phylogenies with multiple homoplasy events.
pubmed:affiliation
School of EECS, University of Central Florida, Orlando, FL 32816-2362, USA. rvijaya@cs.ucf.edu
pubmed:publicationType
Journal Article