Skip Navigation

Bioinformatics 2008 24(13):i105-i113; doi:10.1093/bioinformatics/btn147
This Article
Right arrow Full Text Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Google Scholar
Right arrow Articles by Xie, M.
Right arrow Articles by Chen, J.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Xie, M.
Right arrow Articles by Chen, J.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© 2008 The Author(s)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments and genotype with errors

Minzhu Xie 1,2, Jianxin Wang 1,* and Jianer Chen 1,3

1School of Information Science and Engineering, Central South University, Changsha 410083, 2College of Physics and Information Science, Hunan Normal University, Changsha 410081, China and 3Department of Computer Science, Texas A&M University, College Station, TX 77843, USA

*To whom correspondence should be addressed.


  Abstract

Motivation: In genetic studies of complex diseases, haplotypes provide more information than genotypes. However, haplotyping is much more difficult than genotyping using biological techniques. Therefore effective computational techniques have been in demand. The individual haplotyping problem is the computational problem of inducing a pair of haplotypes from an individual's aligned SNP fragments. Based on various optimal criteria and including different extra information, many models for the problem have been proposed. Higher accuracy of the models has been an important issue in the study of haplotype reconstruction.

Results: The current article proposes a highly accurate model for the single individual haplotyping problem based on weighted fragments and genotypes with errors. The model is proved to be NP-hard even with gapless fragments. Based on the characteristics of Single Nucleotide Polymorphism (SNP) fragments, a parameterized algorithm of time complexity O(nk22k2 + m log m + mk1) is developed, where m is the number of fragments, n is the number of SNP sites, k1 is the maximum number of SNP sites that a fragment covers (no more than n and usually smaller than 10) and k2 is the maximum number of the fragments covering a SNP site (usually no more than 19). Extensive experiments show that this model is more accurate in haplotype reconstruction than other models.

Availability: The program of the parameterized algorithm can be obtained by sending an email to the corresponding author.

Contact: jxwang{at}mail.csu.edu.cn


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.