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.
PDF (1.31 MB PDF FORMAT)
RIS citation (ENDNOTE, REFERENCE MANAGER, PROCITE, REFWORKS)
BibTex citation (BIBDESK, LATEX)
Having just published in a Libertas Academica journal (Evolutionary Bioinformatics) for the first time, I can attest that I was impressed by the process. Every stage from submission to typesetting and correspondence on matters relating to publishing was simple and efficient. In addition to this, regular updates of the status of the manuscript (with clear explanation of the status) enabled the process to be transparent and informative. I would not hesitate to use Libertas Academica ...