Abstract
In this thesis, we address the problem of haplotype decomposition and reconstruction. While focusing on large scale genotype data, we propose a new framework to determine the haplotype block partitions and to resolve the haplotype pair of each genotype. In implementing the decomposition scheme, we formulate a dynamic programming algorithm to minimize the total number of tag SNPs. For structuring the reconstruction method, we introduce an at-least-one perfect-phylogeny-tree model within each block, and use tiling blocks consisting of tag SNPs among blocks. It turns out that the two elements are well coupled and lead to an accurate and efficient haplotype reconstruction system. Our approach is closely related to the work of Eskin et al.. However, the perfect phylogeny model used in their scheme is restricted by only one perfect phylogeny tree within a block. We instead adopt a more flexible criterion that requires at least one perfect phylogeny tree. Furthermore, in dealing with the difficult problem of resolving whole haplotypes among blocks, we go further to take into account all blocks, whereas their work only considers two adjacent blocks. Specifically, the contributions of our work can be characterized by: (i) an at-least-one prefect-phylogeny-tree model, to fit the real genotype data and improve the accuracy of haplotype resolving within a block; (ii) an informative score function, to resolve a genotype into the most likely pair of haplotypes; (iii) tiling blocks consisting of tag SNPs, to make all of the choices resolvable; and (iii) mutual relation among blocks, to resolve whole haplotypes among blocks by considering all blocks, and to reduce the effects caused by a few erratic choices. We have also included various experimental results to illustrate the advantages of the proposed method. Keywords: Haplotype, tag SNPs, perfect phylogeny tree, tiling block