Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments

被引：25

作者：

Chen, Zhixiang ^{[1
]}

Fu, Bin ^{[1
]}

Schweller, Robert ^{[1
]}

Yang, Boting ^{[2
]}

Zhao, Zhiyu ^{[3
]}

Zhu, Binhai ^{[4
]}

机构：

[1] Univ Texas Pan Amer, Dept Comp Sci, Edinburg, TX 78539 USA

[2] Univ Regina, Dept Comp Sci, Regina, SK S4S 0A2, Canada

[3] Univ New Orleans, Dept Comp Sci, New Orleans, LA 70148 USA

[4] Montana State Univ, Dept Comp Sci, Bozeman, MT 59717 USA

来源：

JOURNAL OF COMPUTATIONAL BIOLOGY | 2008年 / 15卷 / 05期

关键词：

inconsistency and incompleteness errors; linear time probabilistic algorithm; probabilistic modeling and analysis; singular haplotype reconstruction; SNP fragments;

D O I：

10.1089/cmb.2008.0003

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

In this paper, we develop a probabilistic model to approach two realistic scenarios regarding the singular haplotype reconstruction problem-the incompleteness and inconsistency that occurred in the DNA sequencing process to generate the input haplotype fragments, and the common practice used to generate synthetic data in experimental algorithm studies. We design three algorithms in the model that can reconstruct the two unknown haplotypes from the given matrix of haplotype fragments with provable high probability and in linear time in the size of the input matrix. We also present experimental results that conform with the theoretical efficient performance of those algorithms. The software of our algorithms is available for public access and for real-time on-line demonstration.

引用

页码：535 / 546

页数：12