title: A Genetic Algorithm for Diploid Genome Reconstruction Using Paired-End Sequencing.
abstract: The genome of many species in the biosphere is a diploid consisting of paternal and maternal haplotypes. The differences between these two haplotypes range from single nucleotide polymorphisms (SNPs) to large-scale structural variations (SVs). Existing genome assemblers for next-generation sequencing platforms attempt to reconstruct one consensus sequence, which is a mosaic of two parental haplotypes. Reconstructing paternal and maternal haplotypes is an important task in linkage analysis and association studies. This study designs and implemented HapSVAssembler on the basis of Genetic Algorithm (GA) and paired-end sequencing. The proposed method builds a consensus sequence, identifies various types of heterozygous variants, and reconstructs the paternal and maternal haplotypes by solving an optimization problem with a GA algorithm. Experimental results indicate that the HapSVAssembler has high accuracy and contiguity under various sequencing coverage, error rates, and insert sizes. The program is tested on pilot sequencing of a highly heterozygous genome, and 12,781 heterozygous SNPs and 602 hemizygous SVs are identified. We observe that, although the number of SVs is much less than that of SNPs, the genomic regions occupied by SVs are much larger, implying the heterozygosity computed using SNPs or k-mer spectrum may be under-estimated.
authors.affiliation: Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan.
authors.forename: Chuan-Kang
authors.initials: CK
authors.lastname: Ting
authors.affiliation: Agricultural Biotechnology Research Center, Academia Sinica, Taipei, Taiwan.
authors.forename: Choun-Sea
authors.initials: CS
authors.lastname: Lin
authors.affiliation: Biotechnology Center in Southern Taiwan, Academia Sinica, Tainan, Taiwan.
authors.forename: Ming-Tsai
authors.initials: MT
authors.lastname: Chan
authors.affiliation: Institute of Biomedical Sciences, National Chung Hsing University, Taichung, Taiwan.
authors.forename: Jian-Wei
authors.initials: JW
authors.lastname: Chen
authors.affiliation: Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan.
authors.forename: Sheng-Yu
authors.initials: SY
authors.lastname: Chuang
authors.affiliation: Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan.
authors.forename: Yao-Ting
authors.initials: YT
authors.lastname: Huang
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D004171:Diploidy; D019143:Evolution, Molecular; D016678:Genome; D023281:Genomics / Q000379:methods*; D006239:Haplotypes; D006579:Heterozygote; D059014:High-Throughput Nucleotide Sequencing; D009154:Mutation; D020641:Polymorphism, Single Nucleotide; D015203:Reproducibility of Results; D017422:Sequence Analysis, DNA; D012984:Software