Dissertations / Theses on the topic 'Haplotype block'

The completion of the human genome project in 2003 paved the way for studies to better understand and catalog variation in the human genome. The International HapMap Project was started in 2002 with the aim of identifying genetic variation in the human genome and studying the distribution of genetic variation across populations of individuals. The information collected by the HapMap project will enable researchers in associating genetic variations with phenotypic variations. Single Nucleotide Polymorphisms (SNPs) are loci in the genome where two individuals differ in a single base. It is estimated that there are approximately ten million SNPs in the human genome. These ten million SNPS are not completely independent of each other - blocks (contiguous regions) of neighboring SNPs on the same chromosome are inherited together. The pattern of SNPs on a block of the chromosome is called a haplotype. Each block might contain a large number of SNPs, but a small subset of these SNPs are sufficient to uniquely dentify each haplotype in the block. The haplotype map or HapMap is a map of these haplotype blocks. Haplotypes, rather than individual SNP alleles are expected to effect a disease phenotype. The human genome is diploid, meaning that in each cell there are two copies of each chromosome - i.e., each individual has two haplotypes in any region of the chromosome. With the current technology, the cost associated with empirically collecting haplotype data is prohibitively expensive. Therefore, the un-ordered bi-allelic genotype data is collected experimentally. The genotype data gives the two alleles in each SNP locus in an individual, but does not give information about which allele is on which copy of the chromosome. This necessitates computational techniques for inferring haplotypes from genotype data. This computational problem is called the haplotype inference problem. Many statistical approaches have been developed for the haplotype inference problem. Some of these statistical methods have been shown to be reasonably accurate on real genotype data. However, these techniques are very computation-intensive. With the international HapMap project collecting information from nearly 10 million SNPs, and with association studies involving thousands of individuals being undertaken, there is a need for more efficient methods for haplotype inference. This dissertation is an effort to develop efficient perfect phylogeny based combinatorial algorithms for haplotype inference. The perfect phylogeny haplotyping (PPH) problem is to derive a set of haplotypes for a given set of genotypes with the condition that the haplotypes describe a perfect phylogeny. The perfect phylogeny approach to haplotype inference is applicable to the human genome due to the block structure of the human genome. An important contribution of this dissertation is an optimal O(nm) time algorithm for the PPH problem, where n is the number of genotypes and m is the number of SNPs involved. The complexity of the earlier algorithms for this problem was O(nm^2). The O(nm) complexity was achieved by applying some transformations on the input data and by making use of the FlexTree data structure that has been developed as part of this dissertation work, which represents all the possible PPH solution for a given set of genotypes. Real genotype data does not always admit a perfect phylogeny, even within a block of the human genome. Therefore, it is necessary to extend the perfect phylogeny approach to accommodate deviations from perfect phylogeny. Deviations from perfect phylogeny might occur because of recombination events and repeated or back mutations (also referred to as homoplasy events). Another contribution of this dissertation is a set of fixed-parameter tractable algorithms for constructing near-perfect phylogenies with homoplasy events. For the problem of constructing a near perfect phylogeny with q homoplasy events, the algorithm presented here takes O(nm^2+m^(n+m)) time. Empirical analysis on simulated data shows that this algorithm produces more accurate results than PHASE (a popular haplotype inference program), while being approximately 1000 times faster than phase. Another important problem while dealing real genotype or haplotype data is the presence of missing entries. The Incomplete Perfect Phylogeny (IPP) problem is to construct a perfect phylogeny on a set of haplotypes with missing entries. The Incomplete Perfect Phylogeny Haplotyping (IPPH) problem is to construct a perfect phylogeny on a set of genotypes with missing entries. Both the IPP and IPPH problems have been shown to be NP-hard. The earlier approaches for both of these problems dealt with restricted versions of the problem, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. We make some novel observations about these problems, and present efficient algorithms for unrestricted versions of these problems. The algorithms have worst-case exponential time complexity, but have been shown to be very fast on practical instances of the problem.<br>Ph.D.<br>Other<br>Engineering and Computer Science<br>Computer Science

Thesis (Ph.D.)--George Mason University, 2009.<br>Vita: p. 123. Thesis director: John J. Grefenstette. Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Bioinformatics and Computational Biology. Title from PDF t.p. (viewed Sept. 8, 2009). Includes bibliographical references (p. 114-122). Also issued in print.

Thesis (Ph. D.)--West Virginia University, 2007.<br>Title from document title page. Document formatted into pages; contains xi, 127 p. : ill. Includes abstract. Includes bibliographical references (p. 109-114).

The method of combination p-values from multiple tests is the foundation for some studies like meta-analysis and detection of signal. There are tremendous methods have been developed and applied like minimum p-values, Cauchy Combination, goodness-of-fit combination and Fisher’s combination. In this paper, I tested their ability to detect signals which is related to real case in biology to find out significant single-nucleotide polymorphisms (SNPs). I simulated p-values for SNPs logistics regression model and test 7 combination methods’ power performance in different setting conditions. I compared sparse or dense signals, dependent or independent and combine them in gene-level or pathway-level. One method based on Fisher’s combination called Omni-TFisher is ideal for most of the situations. Recent years, genome-wide association studies (GWASs) focused on BMD-related SNPs at gene significance level. In this paper I used Omni-TFisher to analyses real data on haplotype blocks. As a result, haplotype blocks can find more SNPs in non-coding and intergeneric regions than gene-based and save computational complexity. It finds out not only known genes, but also other genes need further verification.

Bisherige Methoden der Haplotyp-Block-Definition zielen entweder auf abwesende Rekombinationsereignisse oder eine effiziente Beschreibung genomischer Variation. Die vorliegende Arbeit definiert Blöcke von Single Nucleotide Polymorphisms (SNP) als Gebiete erhöhten Kopplungsungleichgewichtes (LD). Für dieses Ziel wird ein neues, entropie-basiertes Maß für LD zwischen multiplen Markern/Loci (Normalized Entropy Difference) entwickelt und als eine Multilocus-Erweiterung des paarweisen Maßes r2 charakterisiert. Ein zugehöriger Algorithmus für die Block-Definition wird vorgeschlagen. Seine Evaluierung an einem Datensatz des menschlichen Chromosoms 12 vom Internationalen Haplotype Map Projekt zeigt die Nützlichkeit der abgeleiteten Blöcke in Hinblick auf verschiedene Eigenschaften, einschließlich ihrer chromosomalen Coverage und der Anzahl sowie des Anteils der häufigen Block-Haplotypen. Der wesentliche Einfluß der SNP-Dichte auf die zu entdeckenden LD- und Blockstrukturen wird demonstriert. Der Erfolg von Assoziationsstudien in komplexen Erkrankungen mit Block-Haplotypen als multiallelischen Markern wird davon abhängen, ob die Common Variants/Common Diseases (CV/CD) Hypothese für solche Erkrankungen erfüllt ist.<br>Current approaches to haplotype block definition target either absent recombination events or the efficient description of genomic variation. This thesis aims to define blocks of single nucleotide polymorphisms (SNP) as areas of elevated linkage disequilibrium (LD). To this end, a new entropy-based measure for LD between multiple markers/loci, the Normalized Entropy Difference, is developed and is characterized as a multilocus extension of the pairwise measure r2. A corresponding algorithm for the block definition is proposed. Its evaluation on a data set of human chromosome 12 from the International Haplotype Map project proves the usefulness of the derived blocks with respect to several features, including their chromosomal coverage and the number and portion of common block haplotypes. The critical role of the SNP density for detectable LD and block structure is demonstrated. The success of association studies in common diseases with block haplotypes serving as multi-allelic markers will depend on whether the Common Variants/Common Diseases (CV/CD) hypothesis holds true for those diseases.

A associação não aleatória entre alelos de diferentes lócus caracteriza o que é chamado de desequilíbrio de ligação (DL) entre eles. A extensão do DL nas populações humanas pode ser influenciada por muitos fatores, tais como taxa de recombinação, características demográficas (idade, tamanho e taxa de crescimento) e fatores evolutivos (deriva genética, efeito fundador, gargalos populacionais, mutação, seleção e fluxo gênico). Portanto, o conhecimento dos padrões do DL fornecem dados que auxiliam na descrição dos eventos demográficos e evolutivos sofridos pelas populações. O objetivo deste estudo foi descrever os padrões de DL de quatro populações brasileiras e correlacioná-los com suas respectivas histórias demográficas, uma vez que estas populações experimentaram alguns dos eventos evolutivos que geram ou retardam o decréscimo do DL, como fundação por poucos indivíduos, miscigenação no momento da fundação e posterior isolamento. Foram analisadas amostras de três populações remanescentes de quilombos do Estado do Piauí, Gaucinha (GAU, n = 14), Mimbó (MIB, n = 15) e Sítio Velho (STV, n = 15) e da população urbana de Teresina, Piauí (TES, n = 15), além de sete amostras populacionais do projeto HapMap (CEU, CHB, JPT, ASW, LWK, MKK, YRI, todas com n = 15). Foram genotipados mais de 250 mil SNPs (Single Nucleotide Polymorphisms) utilizando-se o GeneChip® Human Mapping 250K Nsp I Array - Affymetrix® nas amostras das quatro populações brasileiras. Os dados brutos das populações do HapMap para este array foram obtidos na página do projeto. Os genótipos para todas as amostras foram determinados pelo algoritmo CRLMM após comparação com o algoritmo BRLMM, e as análises de DL e determinação dos blocos de haplótipos foram realizadas com o uso do programa Haploview. Considerando-se o número de blocos de haplótipos detectados em cada população estudada, padrão semelhante foi observado em todos os autossomos. Em geral, a população europeia (CEU) e as duas populações asiáticas (CHB e JPT) do HapMap apresentaram os maiores números de blocos, enquanto que os menores números foram observados nos quilombos GAU e MIB e na população TES. As populações africanas LWK, MKK e YRI e a população afro-americana ASW apresentaram os valores intermediários e a população afro-brasileira STV, apresentou um número de blocos apenas inferior a CEU, CHB e JPT. A grande contribuição africana nos quilombos GAU e MIB pode explicar o menor DL observado nestas comunidades. Por outro lado, o menor DL em TES se deve, provavelmente, à sua fundação, que envolveu um maior número de indivíduos e foi seguida por um rápido crescimento. A possível explicação para o maior DL observado em STV, em relação aos demais quilombos, consiste em sua peculiar história demográfica: esta comunidade experimentou uma miscigenação no momento de sua fundação, que foi seguida por um crescimento lento e pouca diferenciação. Assim, foi demonstrado como os eventos demográficos de cada população influenciam seus respectivos padrões de DL.<br>The non-random association between alleles of different loci characterizes what is called linkage disequilibrium (LD) between them. The LD extent in human populations can be influenced by many factors, such as recombination rate, demographic features (age, size and growth rate) and evolutionary events (genetic drift, founder effects, population bottlenecks, mutation, selection and gene flow). Therefore, knowledge of the LD patterns provides data that assists in describing the evolutionary and demographic events experienced by populations. The aim of this study was to describe the LD patterns of four Brazilian populations and correlate these patterns with their respective demographic histories, since these populations have experienced some of the evolutionary events that produce or retard the LD decrease, such as foundation by few individuals, admixture at the founding moment and subsequent isolation. Samples from three quilombo remnants populations of the Piauí State, Gaucinha (GAU, n = 14), Mimbó (MIB, n = 15) and Sítio Velho (STV, n = 15) and the urban population of Teresina, Piauí (TES, n = 15), and seven population samples from the HapMap Project (CEU, CHB, JPT, ASW, LWK, MKK, YRI, all with n = 15) were analyzed. More than 250 thousand SNPs (Single Nucleotide Polymorphisms) were genotyped using the GeneChip ® Human Mapping 250K Nsp Array I - Affymetrix ® in the samples of the four Brazilian populations. Raw data of the HapMap population samples for this array were obtained from the HapMap homepage. Genotypes for all samples were determined by CRLMM algorithm after comparison with the BRLMM algorithm. LD analyzes and determination of haplotype blocks were performed using the Haploview software. Considering the number of haplotype blocks detected in each population, a consistent pattern was observed for all autosomes. The European population (CEU) and the two Asian populations (CHB and JPT) of the HapMap showed the highest numbers of blocks, while the lowest numbers were observed in the GAU and MIB quilombos and in the TES population. The African populations, LWK, MKK and YRI, and the African-American ASW exhibited intermediate values and the African-Brazilian population STV, presented a number of blocks smaller than that observed for CEU, CHB and JPT. The great African contribution in the GAU and MIB quilombos may explain the lower LD observed in these communities. On the other hand, the lower LD in TES is probably due to its foundation that involved a larger number of individuals and was followed by a fast growth. A possible explanation for the higher LD observed in STV, compared to other quilombos, consists in its particular demographic history: this community experienced admixture at the time of its foundation, which was followed by slow growth and low differentiation. Thus, it was shown how the demographic events of each population influence their respective LD patterns.

The recently identified (Daly et al. 2001 and Patil et al. 2001) block-like structure in the human genome has attracted much attention since each haplotype block contains limited sequence variation, which can reduce the complexity in genetic mapping studies. This dissertation focuses on estimating haplotype block structures and their application to genetic mapping using single nucleotide polymorphisms (SNPs) from unrelated individuals. Among other issues, the traditional single marker association study leads to the problem of multiple testing, which is still not well understood in the context of genomewide association studies. The haplotype-based approach is one way to lessen certain problems caused by multiple testing. There is also evidence that haplotype based tests have higher statistical power. We first propose a novel approach to estimate haplotype blocks based on pairwise linkage disequilibrium (LD). The application to simulated data shows that our new approach has higher power than several existing methods in identifying haplotype blocks. We also examine the impact of marker density and different tagging strategies on the estimation of haplotype blocks. We introduce a new statistic to measure the difference between two different block partitions. Applying the new statistic to real and simulated data we show that a higher marker density is needed than previously expected in order to recover the true block structure over a given region. Finally, we analyzed a real SNP data set. A comparison of the haplotype-SNP based method to the more traditional single-SNP based method shows that the two methods tend to agree more when halplotype block sizes are small. On the other hand, the haplotype-SNP based approach does not always have higher power than the single-SNP based study as is supported by theoretical considerations. Indeed, long haplotype blocks where the LD structure might be very complex can lead to inferior power compared to single-SNP approaches. In practice, it is recommended that single-SNP analyses be run routinely, especially in the presence of moderate to long blocks.

碩士<br>國立中山大學<br>資訊工程學系研究所<br>92<br>SNP (single nucleotide polymorphisms, pronounce as snip) is one nucleotide position difference within human population. These differences can be detected in human genome and the difference occurs once about every 1000 base pairs. There are only two possible nucleotides in each SNP position. As a genetic marker, SNP data can be used to capture human disease traits because of its abundance and low diversity. In recent research results, it has been shown that there is a block-like structure in human genome, and only limited haplotype diversity can be observed. Consequently, we can use only a small fraction of SNPs to capture haplotype diversity in each block, and these SNPs are called tagSNPs. We propose a fixed-diversity approach to capture the diversity of the entire data. After partitioning the haplotype blocks, we will provide an objective way for evaluating the result. We obtain that the diversity of chromosome 21 SNPs locates at 0.5 by using our algorithm. The partition result shows the concurrence property of the haplotype data downloaded from NCBI web site. Finally, we develop an algorithm for tagSNP selection within each block, and obtain the compression ratio 0.78.

碩士<br>靜宜大學<br>資訊工程學系<br>101<br>SNPs play important roles for various analysis applications including medical diagnostic and drug design. They contain the highest-resolution genetic fingerprint for identifying disease associations and human features. Haplotype, is composed of SNPs, region of linked genetic variants that are neighboring usually inherited together. Recently, genetics researches show that SNPs within certain haplotype blocks induce only a few distinct common haplotypes in the majority of the population. The discussion of haplotype block has serious implications of method with association-based for the disease genes mapping. We proposed the method in investigating several efficient combinatorial algorithms related to selecting interesting haplotype blocks under different diversity functions that generalizes many previous results in the literatures. However, the proposed method is computation-consuming. This thesis adopts approach using the MapReduce paradigm to parallelize tools and manage their execution. The experiment shows that the map/reduce-paralleled from the original sequential combinatorial algorithm performs well on the real-world data obtained in from the HapMap data set; the computation efficiency can be effectively improved proportional to the number of processors being used.

碩士<br>靜宜大學<br>資訊管理學系研究所<br>94<br>Global patterns of human DNA sequence variation (haplotypes) defined by common single nucleotide polymorphisms (SNPs) have important implications for identifying disease associations and human traits. Recent genetics research reveals that SNPs within certain haplotype blocks induce only a few distinct common haplotypes in the majority of the population. The existence of haplotype block structure has serious implications for association-based methods for the mapping of disease genes. Our ultimate goal is to select haplotype block designations that best capture the structure within the data. Here in this thesis we propose several efficient combinatorial algorithms related to selecting interesting haplotype blocks under different diversity functions that generalizes many previous results in the literatures. For dealing with missing SNP data, we show in this thesis that the "Minimum Diversity Problem" is NP-complete and propose a heuristic agorithm to deal with these sites.

A dissertation submitted to the Faculty of Science, University of the Witwatersrand, in fulfillment of the requirements for the degree of Master of Science Johannesburg, August 2012<br>It is known that infectious agents elicit different responses in different individuals which strengthens the view that susceptibility and resistance to infectious diseases has a genetic component. These differences in susceptibility to disease can be observed in populations. APOBEC3G is a member of the cytidine deaminase gene family located on chromosome 22. It is crucial in non-permissive cells as it functions as part of the innate immunity system and is an inhibitor of the HIV-1 accessory protein vif. The goal of the study was to develop genotyping assays and estimate allele frequencies. Thus, genetic variation within APOBEC3G was identified and characterized in black South Africans. Indirect genotyping assays were designed to amplify regions within the upstream non-coding region, and in exon 4 of the coding region of the gene. Selected polymorphisms were then genotyped using allele-specific PCR, RFLP-PCR and Pyrosequencing™ assays. Reanalysis of sequence data from 2003 showed numerous SNPs were well represented. Comparison of sequence data at various SNPs showed that allele frequencies were similar to frequencies in other African populations. The only sequenced SNP that deviated from the frequencies in Ensembl was -590. Thus the sequencing was a useful tool for detection of variation. ASA proved to be the least reliable genotyping technique as the minor allele frequency of -571 (0.59) deviated from the published frequency of 0.894 in Africans. RFLP analysis proved more reliable for genotyping -571 and H186R. The minor allele frequency was estimated to be 0.84 and 0.32 for -571 and H186R respectively. The frequency of H186R is similar to published data from An et al (2004) and Reddy et al (2010). If SNPs are in LD they occur together on the same haplotype more often than by chance. Usually SNPs that are in LD are in close proximity. However our data suggests -571 and H186R SNPs which are 5kb apart are not in LD. A LD map of chromosome 22 shows highly variable pattern of LD (Dawson et al, 2002). Widespread regions of nearly complete LD up to 804 kb in length are intermingled with regions of little or uundetectable LD. Haplotype analysis showed the most frequent haplotype was GA. This was the most frequent haplotype when the sample types were subdivided according to spoken language. in comparison to studies from An et al, (2004) D’ of the two SNPs was estimated at 0.967. The linkage disequilibrium (LD) revealed a non-independence of allele segregation because the loci analyzed were strongly linked in the Apobec 3 G gene. The data are consistent with greater genetic diversity of African populations and can form the basis for further evaluation of the role of variation in this gene in response to HIV.

Heritable variation is important in disease progression, therefore its association with HIV/AIDS was analyzed. APOBEC3G is a unique cellular gene that influences HIV infectivity. It belongs to family of cytidine deaminases and is both an RNA and DNA editing enzyme. APOBEC3G is a good candidate for HIV restriction because it allows the expression of an antiviral phenotype in non-permissive cells consequently this innate immune defense may provide the basis for the design of new therapies for HIV. Variation in the upstream non-coding region of APOBEC3G was studied. Six base variants were found at positions -90, -163, -166, -571, -590 and -821. In addition, promoter analysis identified promoters in the upstream non-coding region. Indirect genotyping assays were developed to genotype the participants at -571 and H186R. The frequency of -571 GG was 70 %. The frequency of the TT genotype of H186R was 20 %. The GG genotype was selected against in the HIV + group of the study participants. This is indicative that this SNP has disease modifying effects. The TT genotype was related to increased progression to AIDS confirming the results of previous studies.