title: FISH: fast and accurate diploid genotype imputation via segmental hidden Markov model.
abstract: BACKGROUND
  Fast and accurate genotype imputation is necessary for facilitating gene-mapping studies, especially with the ever increasing numbers of both common and rare variants generated by high-throughput-sequencing experiments. However, most of the existing imputation approaches suffer from either inaccurate results or heavy computational demand.
  
  
  RESULTS
  In this article, aiming to perform fast and accurate genotype-imputation analysis, we propose a novel, fast and yet accurate method to impute diploid genotypes. Specifically, we extend a hidden Markov model that is widely used to describe haplotype structures. But we model hidden states onto single reference haplotypes rather than onto pairs of haplotypes. Consequently the computational complexity is linear to size of reference haplotypes. We further develop an algorithm 'merge-and-recover (MAR)' to speed up the calculation. Working on compact representation of segmental reference haplotypes, the MAR algorithm always calculates an exact form of transition probabilities regardless of partition of segments. Both simulation studies and real-data analyses demonstrated that our proposed method was comparable to most of the existing popular methods in terms of imputation accuracy, but was much more efficient in terms of computation. The MAR algorithm can further speed up the calculation by several folds without loss of accuracy. The proposed method will be useful in large-scale imputation studies with a large number of reference subjects.
  
  
  BACKGROUND
  The implemented multi-threading software FISH is freely available for academic use at https://sites.google.com/site/lzhanghomepage/FISH.
authors.affiliation: School of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, ChinaSchool of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, China.
authors.forename: Lei
authors.initials: L
authors.lastname: Zhang
authors.affiliation: School of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, ChinaSchool of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, China.
authors.forename: Yu-Fang
authors.initials: YF
authors.lastname: Pei
authors.affiliation: School of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, China.
authors.forename: Xiaoying
authors.initials: X
authors.lastname: Fu
authors.affiliation: School of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, China.
authors.forename: Yong
authors.initials: Y
authors.lastname: Lin
authors.affiliation: School of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, China.
authors.forename: Yu-Ping
authors.initials: YP
authors.lastname: Wang
authors.affiliation: School of Public Health, Xi'an Jiaotong University, Shaanxi, China, Department of Biostatistics and Bioinformatics, Tulane University, New Orleans, USA and Center of System Biomedical Sciences, University of Shanghai for Science and Technology, Shanghai, China.
authors.forename: Hong-Wen
authors.initials: HW
authors.lastname: Deng
mesh_terms: D000465:Algorithms; D004171:Diploidy; D005838:Genotype; D006239:Haplotypes; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D008390:Markov Chains; D012984:Software