TY - GEN
T1 - Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments
AU - Chen, Zhixiang
AU - Fu, Bin
AU - Schweller, Robert
AU - Yang, Boting
AU - Zhao, Zhiyu
AU - Zhu, Binhai
PY - 2008/12/1
Y1 - 2008/12/1
N2 - In this paper, we develop a probabilistic model to approach two scenarios in reality about the singular haplotype reconstruction problem - the incompleteness and inconsistency 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 time linear 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.
AB - In this paper, we develop a probabilistic model to approach two scenarios in reality about the singular haplotype reconstruction problem - the incompleteness and inconsistency 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 time linear 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.
KW - Haplotype reconstruction
KW - Incompleteness errors
KW - Inconsis- tency errors
KW - Probabilistic algorithms
KW - SNP fragments
UR - http://www.scopus.com/inward/record.url?scp=84863115946&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863115946&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84863115946
SN - 9781848161085
T3 - Series on Advances in Bioinformatics and Computational Biology
SP - 333
EP - 342
BT - Proceedings of 6th Asia-Pacific Bioinformatics Conference, APBC 2008
T2 - 6th Asia-Pacific Bioinformatics Conference, APBC 2008
Y2 - 14 January 2008 through 17 January 2008
ER -