https://scholars.lib.ntu.edu.tw/handle/123456789/315313
標題: | An approximation algorithm for haplotype inference by maximum parsimony | 作者: | Huang, Y.-T. KUN-MAO CHAO Chen, T. |
關鍵字: | Algorithm; Haplotype inference; Integer quadratic programming; Maximum parsimony; Semi-definite programming | 公開日期: | 2005 | 卷: | 12 | 期: | 10 | 起(迄)頁: | 1261-1274 | 來源出版物: | Journal of Computational Biology | 摘要: | This paper studies haplotype inference by maximum parsimony using population data. We define the optimal haplotype inference (OHI) problem as given a set of genotypes and a set of related haplotypes, find a minimum subset of haplotypes that can resolve all the genotypes. We prove that OHI is NP-hard and can be formulated as an integer quadratic programming (IQP) problem. To solve the IQP problem, we propose an iterative semi-definite programming-based approximation algorithm, (called SDPHapInfer). We show that this algorithm finds a solution within a factor of O(log n) of the optimal solution, where n is the number of genotypes. This algorithm has been implemented and tested on a variety of simulated and biological data. In comparison with three other methods, (1) HAPAR, which was implemented based on the branching and bound algorithm, (2) HAPLOTYPER, which was implemented based on the expectation-maximization algorithm, and (3) PHASE, which combined the Gibbs sampling algorithm with an approximate coalescent prior, the experimental results indicate that SDPHapInfer and HAPLOTYPER have similar error rates. In addition, the results generated by PHASE have lower error rates on some data but higher error rates on others. The error rates of HAPAR are higher than the others on biological data. In terms of efficiency, SDPHapInfer, HAPLOTYPER, and PHASE output a solution in a stable and consistent way, and they run much faster than HAPAR when the number of genotypes becomes large. © Mary Ann Liebert, Inc. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33645011046&doi=10.1089%2fcmb.2005.12.1261&partnerID=40&md5=6181e95e5e119379cf3ce6468493cf5d http://scholars.lib.ntu.edu.tw/handle/123456789/315313 |
ISSN: | 10665277 | DOI: | 10.1089/cmb.2005.12.1261 |
顯示於: | 生醫電子與資訊學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。