title: RadixHap: a radix tree-based heuristic for solving the single individual haplotyping problem.
abstract: Single nucleotide polymorphism studies have recently received significant amount of attention from researchers in many life science disciplines. Previous researches indicated that a series of SNPs from the same chromosome, called haplotype, contains more information than individual SNPs. Hence, discovering ways to reconstruct reliable Single Individual Haplotypes becomes one of the core issues in the whole-genome research nowadays. However, obtaining sequence from current high-throughput sequencing technologies always contain inevitable sequencing errors and/or missing information. The SIH reconstruction problem can be formulated as bi-partitioning the input SNP fragment matrix into paternal and maternal sections to achieve minimum error correction; a problem that is proved to be NP-hard. In this study, we introduce a greedy approach, named RadixHap, to handle data sets with high error rates. The experimental results show that RadixHap can generate highly reliable results in most cases. Furthermore, the algorithm structure of RadixHap is particularly suitable for whole-genome scale data sets.
authors: Centre for Distributed and High Performance Computing, School of Information Technologies, University of Sydney, NSW 2006, Australia.
authors: Tai-Chun
authors: TC
authors: Wang
authors: Centre for Distributed and High Performance Computing, School of Information Technologies, University of Sydney, NSW 2006, Australia.
authors: Javid
authors: J
authors: Taheri
authors: Centre for Distributed and High Performance Computing, School of Information Technologies, University of Sydney, NSW 2006, Australia.
authors: Albert Y
authors: AY
authors: Zomaya
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D004247:DNA / Q000235:genetics*; D004252:DNA Mutational Analysis / Q000379:methods*; D006239:Haplotypes / Q000235:genetics*; D006801:Humans; D008969:Molecular Sequence Data; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012984:Software
chemical_list: D004247:DNA
keywords: SNPs; bioinformatics; gene sequencing; greedy algorithm; minimum error correction; radix tree; single individual haplotypes; single nucleotide polymorphisms; whole genome data sets