ALGORITHMS FOR COMPUTATIONAL GENETIC EPIDEMIOLOGY by Jingwu He Under the Direction of Alex Zelikovsky ABSTRACT The most intriguing problems in genetics epidemiology are to predict genetic disease susceptibility and to associate single nucleotide polymorphisms (SNPs) with diseases. In such these studies, it is necessary to resolve the ambiguities in genetic data. The primary obstacle for ambiguity resolution is that the physical methods for separating two haplotypes from an individual genotype (phasing) are too expensive. Although computational haplotype inference is a well-explored problem, high error rates continue to deteriorate association accuracy.
Secondly, it is essential to use a small subset of informative SNPs (tag SNPs) accurately representing the rest of the SNPs (tagging). Tagging can achieve budget savings by genotyping only a limited number of SNPs and computationally inferring all other SNPs. Recent successes in high throughput genotyping technologies drastically increase the length of available SNP sequences. This elevates importance of informative SNP selection for compaction of huge genetic data in order to make feasible fine genotype analysis.
Finally, even if complete and accurate data is available, it is unclear if common statistical methods can determine the susceptibility of complex diseases. The dissertation explores above computational problems with a variety of methods, including linear algebra, graph theory, linear programming, and greedy methods. The contributions include (1)significant speed-up of popular phasing tools without compromising their quality, (2)stat-of-the-art tagging tools applied to disease association, and (3)graph-based method for disease tagging and predicting disease susceptibility. INDEX WORDS: Tagging, Phasing, Haplotype, Genotype, SNP, Disease association, Susceptibility prediction ALGORITHMS FOR COMPUTATIONAL GENETIC EPIDEMIOLOGY by Jingwu He A Dissertation Submitted in Partial Fulfillment of Requirements for the Degree of Doctor of Philosophy in the College of Arts and Sciences Georgia State University 2006 UMI Number: 3243235 Copyright 2006 by He, Jingwu All rights reserved.
UMI Microform 3243235 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.
Box 1346 Ann Arbor, MI 48106-1346 Copyright by Jingwu He 2006 ALGORITHMS FOR COMPUTATIONAL GENETIC EPIDEMIOLOGY by Jingwu He Major Professor: Alex Zelikovsky Committee: Yi Pan Anu Bourgeois Ion Mandoiu Electronic Version Approved: Office of Graduate Studies College of Arts and Sciences Georgia State University December 2006 DEDICATION To my dear daughter, Jennifer, my wife, Jun and my parents iv ACKNOWLEDGMENTS First, I would like to thank my advisor, Dr. Alexander Zelikovsky for advising and guide for my Ph. Secondly, I want to thank my dissertation committee members, Dr. Yi Pan, Dr.
Anu Bourgeois and Dr. I also appreciate support and assistance from our research group: Dumitru Brinza, Kelly Westbrooks, Weidong Mao and Nisar Hundewale. Finally, I want to thank my family and friends for their support and beliefs. v TABLE OF CONTENTS Page DEDICATION.
v LIST OF TABLES. ix LIST OF FIGURES .1 Road Map and Contributions. BIOLOGY BACKGROUND: SNPS, HAPLOTYPES, GENOTYPES, AND NOTATIONS. HAPLOTYPE INFERENCE PROBLEM .1 Population Haplotype Inference Problem .1 Previous Work and Problem Formulation .2 Linear Dependence of Sites, Haplotypes and Genotypes .3 Implementation of Linear Reduction Based on Matrix Multiplication .4 Fixing Caveats in Linear Reduction Approach .2 Phasing and Missing data recovery in Family Trios .1 Previous Work and Problem Formulation .2 Pure-Parsimony Trio Phasing .3 Integer Linear Program for Trio Phasing .4 Greedy Method for Trio Phasing.
INFORMATIVE SNP SELECTION .2 Linear Algebraic Method .1 Linear Algebraic Tagging .2 Linear Algebraic Tagging with Prescribed Number of Tags .3 Tag SNP Selection and SNP Prediction Problems .4 Multiple Linear Regression SNP Prediction Method .1 Introduction to Multiple Linear Regression .2 The MLR SNP Prediction Algorithm .3 Running Time of MLR SNP prediction and Tag Selection .5 MLR-tagging Software .5 Support Vector Machine SNP Prediction Method .2 SVM Haplotype Tagging .4 SVM-tagging Software .6 Application of Tagging to Disease Association Search .1 Multi-SNP to Disease Association .3 Searching Methods for Disease Association. DISEASE SUSCEPTIBILITY PREDICTION .3 Measures of Prediction Quality and Cross-validation Methods .2 Reduction to Set Covering Problem .3 Set Covering Greedy Algorithm .3 Prediction Algorithms for Disease Susceptibility .2 Graph-based Prediction Methods. CONCLUSION AND FUTURE WORK .1 Unbiased Estimates of MLR Tagging .2 Protein substrate prediction .3 Simulation of behavior of bacterial cells under specific growth conditions. 118 viii LIST OF TABLES Table Page 3.1 The comparison of the running times of DPPH and Linearly Reduced DPPH.
Each value is averaged over 100 datasets. E and D is the CPU time for encoding and decoding and RD is DPPH runtime for the reduced instance.2 The comparison of the running times of PHASE and Linearly Reduced PHASE. Each value is averaged over 25 datasets.3 The comparison of the quality of haplotyping of Linearly Reduced PHASE (LRP) and PHASE (P) vs the original haplotypes (O). Here the difference in haplotype data sets, Hapset1/Hapset2 is the arithmetic mean of numbers of false-positive and false-negative haplotypes over the number of haplotypes Hapset2 times 100%.
Each value is averaged over 25 datasets.4 The comparison of the quality of haplotyping of Linearly Reduced PHASE (LRP) and PHASE (P) vs the original haplotypes (O). Here the difference in haplotype data sets, Hapset1/Hapset2 is the arithmetic mean of numbers of false-positive and false-negative haplotypes over the number of haplotypes Hapset2 times 100%. Each value is averaged over feasible graphs among 25 datasets.5 The comparison of the running times of HAPLOTYPER and Linearly Reduced HAPLOTYPER. Each value is averaged over 25 datasets.6 The comparison of the quality of haplotyping of Linearly Reduced HAPLOTYPER (LRH) and HAPLOTYPER (H) vs the original haplotypes (O).
Here the difference in haplotype data sets, Hapset1/Hapset2 is the arithmetic mean of numbers of false-positive and false-negative haplotypes over the number of haplotypes Hapset2 times 100%. Each value is averaged over feasible graphs among 25 datasets.7 The comparison of the quality of haplotyping of Linearly Reduced HAPLOTYPER (LRH) and HAPLOTYPER (H) vs the original haplotypes (O). Here the difference in haplotype data sets, Hapset1/Hapset2 is the arithmetic mean of numbers of false-positive and false-negative haplotypes over the number of haplotypes Hapset2 times 100%. Each value is averaged over feasible graphs among 25 datasets.8 The comparison of the running times on real data.9 The comparison of Linearly Reduced HAPLOTYPER (LRH), HAPLOTYPER(H), Linearly Reduced PHASE (LRP), PHASE (P), and original haplotypes (O) on biological data.10 The results for three phasing methods on the real data sets [26, 32, 54] and simulated data set.
Error% is the percent sites where (best choice of) paternal and maternal haplotypes disagree with the offspring genotype. D % is the Hamming distance between the phased haplotypes and the closest feasible haplotypes.11 The comparison of the running times, number of variables, number of constraints of three linear programs. Each value is averaged over all blocks. All phasing block sizes are uniform.12 The results for five phasing methods on the real data sets of Daly et al.[26], Gabrile et al.
[32] and on simulated data. The second column corresponds to the ratio of erased data. The C corresponds to the logical error of child. The P corresponds to the logical error of parents.
The T corresponds to the total logical error.13 The results for five phasing methods on the simulated data sets. The column E represents the percent of erased data. The C corresponds to the true error of child. The P corresponds to the true error of parents.
The T corresponds to the true total error.14 The results for missing data recovery on the real and simulated data sets with five methods. The second column corresponds to the ratio of erased data. The C* corresponds to the error of child. The P* corresponds to the error of parents.
The T* corresponds to the total error.1 The quality of SNP prediction from the given number of tags (5% to 15% of the total number of SNPs (in Parentheses). The prediction quality is measured by the prediction accuracy and the average and minimum R2. Total number of SNPs in each dataset is in the parenthesis.2 Number of tags used by MLR-tagging, STAMPA and LR to achieve 80% and 90% prediction accuracy in leave-one-out tests.3 The comparison of MLR’s and STAMPA’s prediction accuracy and running time by using the number of tags (2, 5, 10, 15, 20, 25) on region ENr123 (A) and ENm010 (B) from 2 population: Han Chinese (HCB) and Japanese (JRT). Total number of SNPs in each dataset is in the parenthesis.4 The quality of MLR/STA on Daly et al.
[26] data with two different tagging objectives over different number of tag SNPs.5 The number of tag SNPs for statistical covering of all SNPs required by three methods: MLR/STA with prediction objective, MLR/STA with statistical covering objective, and IdSelect [16].6 Leave-one-out tests are performed on 3 real haplotype datasets. The minimum number of tag SNPs needed to reach from 80% to 99% prediction accuracy is listed. The bold numbers indicate cases when the SVM/STA needs fewer tags than the MLR method of He et al. [45] for reaching same prediction accuracy.7 The comparison of our proposed SVM/STA method and the MLR method of He et al.
[45] over different number of tag SNPs.8 Comparison of four methods for searching disease-associated multi-SNPs combinations.1 Classification contingency table .2 The comparison of the prediction rates of 6 prediction methods for Crohn’s Disease (Daly et al.)[26] and autoimmune disorder (Ueda et al. Genotype data are phased by 4 methods. GERBIL [37]and PHASE [87] are statistical tools for haplotype reconstruction. For Crohn’s Disease, GERBIL feasible and PHASE feasible find the respective closest feasible haplotypes of the trio data.3 The comparison of the prediction rates of two prediction methods (Second Neighbor and Haplotype Weighting) on Daly et al.
[26] phased by GERBIL [37] and GERBIL Feasible. We report bootstrapping rates, i., the 5th worst rate out of 100 runs (95% confidence) and different bootstrapping rates – averaged over 100 random choices of 20 case and 200 control genotypes. 107 xii LIST OF FIGURES Figure Page 1.1 DNA, gene, chromosome, genome .1 An example of Haplotype Inference Problem .2 2SNP Phasing Algorithm .3 An graph representation of Haplotype Inference Problem .4 The Decoding Algorithm.5 (a) The reduced haplotype graph with 3 vertices.6 Resolve child’s haplotypes .1 Problem formulation of Informative SNP Selection .2 Simulated data with 25000 sites and haplotype population 1000. The total number of errors in % to the total number of SNPs depending on the size of the sample population for the three algorithms LR, RLR, RLRP and 3RLRP.3 The dataset of 158 haplotypes with 103 SNPs from [26].
The total number of errors in % to the total number of SNPs depending on the size of the sample population for the three algorithms LR, RLR, RLRP and 3RLRP.4 The dataset of 158 haplotypes with 103 SNPs from [26]. The total number of errors in % to the total number of SNPs depending on the number of the tags for algorithms RLRP and 3RLRP.5 Simulated data with 25000 sites and different sizes of haplotype population. The total number of errors in % to the total number of SNPs depending on the size of the sample population for the different population sizes (p = 300, 500, 1000, 2000).6 The x-axis shows the number of zeros in each column of R of the haplotype matrix and the y-axis shows reconstruction error rate for each column in the sample using the RLRP method.7 (A) The total number of errors as a percentage of the total number of SNPs depending on the size of the sample population for the three algorithms LRP, RLRP, and SLT on Chromosome 5q31. (B) The total number of errors as a percentage of total number of SNPs depending on the size of the sample population and the percentage of missing data for the SLT method on Chromosome 5q31.8 The x-axis shows the number of tag SNPs, and the y-axis shows the fraction of SNPs correctly imputed in a leave-one-out experiment.