Close
Help
Need Help?





JOURNAL

Evolutionary Bioinformatics

1,045,378 Journal Article Views | Journal Analytics

Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype

Submit a Paper



Publication Date: 16 Feb 2007

Journal: Evolutionary Bioinformatics

Citation: Evolutionary Bioinformatics 2006:2 261-270

Xiang-Sun Zhang1, Rui-Sheng Wang2, Ling-Yun Wu1 and Wei Zhang3

1Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China. 2School of Information, Renmin University of China, Beijing 100872. 3North Carolina State University, Raleigh, NC 27695-7906, U.S.A.

Abstract: The Minimum Error Correction (MEC) is an important model for haplotype reconstruction from SNP fragments. However, this model is effective only when the error rate of SNP fragments is low. In this paper, we propose a new computational model called Minimum Conflict Individual Haplotyping (MCIH) as an extension to MEC. In contrast to the conventional approaches, the new model employs SNP fragment information and also related genotype information, thereby a high accurate inference can be expected. We first prove the MCIH problem to be NP-hard. To evaluate the practicality of the new model we design an exact algorithm (a dynamic programming procedure) to implement MCIH on a special data structure. The numerical experience indicates that it is fairly effective to use MCIH at the cost of related genotype information, especially in the case of SNP fragments with a high error rate. Moreover, we present a feed-forward neural network algorithm to solve MCIH for general data structure and large size instances. Numerical results on real biological data and simulation data show that the algorithm works well and MCIH is a potential alternative in individual haplotyping.


Downloads

PDF  (1.31 MB PDF FORMAT)

RIS citation   (ENDNOTE, REFERENCE MANAGER, PROCITE, REFWORKS)

BibTex citation   (BIBDESK, LATEX)

XML






What Your Colleagues Say About Evolutionary Bioinformatics
I found the submission management system for Evolutionary Bioinformatics to be one of the most user-friendly around. The peer review was very rigorous and constructive. Support staff were polite and furnished accurate information almost instantly. I strongly recommend other scientists to consider this journal.
Dr Madhav Nepal (South Dakota State University, Brookings, SD, USA)
More Testimonials

Quick Links




Follow Us We make it easy to find new research papers.




SUBJECT HUBS
Author Survey Results
author_survey_results
All authors are surveyed after their articles are published. Authors are asked to rate their experience in a variety of areas, and their responses help us to monitor our performance. Presented here are their responses in some key areas. No 'poor' or 'very poor' responses were received; these are represented in the 'other' category.
See Our Results