title: Semi-supervised clustering algorithm for haplotype assembly problem based on MEC model.
abstract: Haplotype assembly is to infer a pair of haplotypes from localized polymorphism data. In this paper, a semi-supervised clustering algorithm-SSK (semi-supervised K-means) is proposed for it, which, to our knowledge, is the first semi-supervised clustering method for it. In SSK, some positive information is firstly extracted. The information is then used to help k-means to cluster all SNP fragments into two sets from which two haplotypes can be reconstructed. The performance of SSK is tested on both real data and simulated data. The results show that it outperforms several state-of-the-art algorithms on minimum error correction (MEC) model.
authors.affiliation: School of Computer Science and Technology, Shandong University, Jinan 250101, China. xuxinshun@sdu.edu.cn
authors.forename: Xin-Shun
authors.initials: XS
authors.lastname: Xu
authors.forename: Ying-Xin
authors.initials: YX
authors.lastname: Li
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D020869:Gene Expression Profiling / Q000379:methods; D006239:Haplotypes; D020641:Polymorphism, Single Nucleotide