Academic literature on the topic 'Haplotype assembly'

Il genoma di ogni individuo nella popolazione umana è caratterizzato univocamente da un insieme di varianti genomiche che distinguono il suo DNA da ogni altro. Perciò, studiare la relazione tra queste varianti e le differenze osservabili negli individui è fondamentale per molte applicazioni mediche. Per identificare queste varianti, le tecnologie di sequenziamento producono un’enorme quantità di frammenti di DNA. Tuttavia, questi frammenti danno solo una visione approssimativa del DNA di un individuo, perché sono molto più corti, contengono diversi errori e sono ottenuti considerando milioni di cellule contemporaneamente. Di conseguenza, l’inferenza di varianti genomiche da questi frammenti è uno dei problemi principali in biologia computazionale, una branca dell’informatica che progetta algoritmi per affrontare problemi derivanti da dati biologici. Il mio lavoro di ricerca in questa tesi si colloca in questo contesto e si focalizza su due problemi che riguardano, difatti, l’inferenza di varianti genomiche da dati di sequenziamento. Per questi problemi ho adottato un approccio basato su ottimizzazione combinatoria per il quale ho introdotto nuove formulazioni combinatorie e relativi algoritmi, sfruttato caratteristiche specifiche del contesto. Il primo problema riguarda la ricostruzione dei due aplotipi di un individuo, ognuno dei quali corrisponde all’insieme di sequenze di DNA ereditate da ognuno dei due genitori. La loro ricostruzione è fondamentale per caratterizzare il genoma umano, visto che i due aplotipi sono distinti da diverse varianti genomiche. La forma piu’ frequente di varianti genomiche negli aplotipi sono i Single-Nucleotice Polymorphisms (SNPs). L’assemblaggio di aplotipi è l’approccio che cerca di ricostruire gli aplotipi e i loro SNPs a partire da frammenti di sequenziamento. Anzitutto, in questa tesi mi sono occupato di studiare la complessità parametrica e l’approssimazione di tradizionali formulazioni combinatorie di questo problema, tra cui la correzione del minimo numero di errori (MEC). Infatti, metodi basati su questi approcci hanno mostrato ottimi risultati preliminari su dati reali. Inoltre, sfruttando le caratteristiche dei frammenti prodotti dalle nuove tecnologie, quali la lunghezza aumentata e la distribuzione uniforme degli errori, ho introdotto una nuova formulazione combinatoria del problema. Per questa, ho progettato un nuovo algoritmo, chiamato HapCol, che si è rivelato in grado di migliorare i risultati ottenuti da metodi tradizionali sia su dati simulati che reali. Il secondo problema riguarda l’identificazione e quantificazione dei cloni di un singolo tumore. Infatti, un tumore deriva da un processo evolutivo in cui nuove mutazioni vengono accumulate durante la vita di un individuo in diverse cellule, risultando in distinte sottopopolazioni di cellule, chiamate cloni, ognuna delle quali è caratterizzata da una combinazione unica di varianti genomiche. L’identificazione di questi cloni, delle loro proporzioni e della loro storia evolutiva si è rivelato di fondamentale importanza sia per la diagnosi che la prognosi di tumori. In particolare, mi sono focalizzato su mutazioni frequenti nei tumori, chiamate Copy-Number Aberrations (CNAs) che amplificano o eliminano copie di segmenti genomici. Perciò, ho introdotto nuove formulazioni combinatorie che mirano ad identificare i diversi cloni distinti da queste mutazioni e la loro evoluzione a partire da frammenti di sequenziamento ottenuti da più campioni dello stesso tumore e contenenti cellule di cloni diversi. Ho studiato la loro complessita’ computazionale e ho disegnato algoritmi, basati su programmazione lineare intera e su strategie di “discesa delle coordinate”, che si sono rivelati in grado di gestire istanze di dimensioni reali su dati simulati, mentre, su dati derivanti da un tumore alla prostata, hanno offerto una visione ad alta risoluzione dei suoi cloni in termini di CNAs.<br>The genome of any individual in the human population is characterized by a unique complement of genomic variants distinguishing its DNA from any other. As such, studying the relationship between genomic variants and observable traits in human individuals is important for many applications in medicine. To identify these variants, current sequencing technologies produce a huge amount of DNA fragments, called reads. Unfortunately, these reads do not offer a complete and exact view of the DNA sequence since they are orders of magnitude shorter than the source, contain errors, and are obtained by considering millions of different cells together. As such, the inference of genomic variants from sequencing reads is one of the main problems in computational biology, a branch of computer science that designs algorithms for answering biological questions. The work of my thesis belongs to this context and is hence focused on the inference of genomic variants from sequencing reads. I adopt an approach based on combinatorial optimization to introduce new problem formulations and related algorithms by exploiting characteristics specific to the context. The first problem concerns the assembly of the two haplotypes contained in each cell of a human individual. A haplotype corresponds to the set of DNA sequences inherited from each parent. Since the two haplotypes comprise different genomic variants, their reconstruction is crucial for characterizing the genome of an individual: Single-Nucleotide Polymorphisms (SNPs) are the most common form of genomic variants between the two haplotypes. Haplotype Assembly is the approach that aims to reconstruct the two haplotypes and their SNPs from sequencing reads. First, in this thesis I study the parameterized tractability and approximability of traditional combinatorial problems for this approach, especially the Minimum Error Correction (MEC). In fact, methods based of these frameworks revealed preliminary good results on real data. Next, I introduce a new combinatorial formulation of MEC by exploiting the characteristics of reads produced by “future-sequencing” technologies, such as the longer reads and the uniform distribution of sequencing errors. For this problem, I design a dynamic-programming algorithm, HapCol, that outperforms current state-of-the-art methods on both simulated and real data. The second problem concerns the quantification of intra-tumor heterogeneity. Cancer results from an evolutionary process where somatic mutations accumulate in different cells during the lifetime of an individual. As such, a tumor comprises distinct subpopulations of cells, or clones, sharing a unique complement of genomic variants. The identification of these clones, their proportions, and their evolutionary history is crucial to both diagnosis and prognosis of cancer. Here, I focus on Copy-Number Aberrations (CNAs) that are mutations amplifying or deleting the copies of genomic segments. In this thesis, I introduce new combinatorial formulations of problems that aim to quantify the distinct clones in terms of CNAs and to infer their evolution from sequencing reads of multiple heterogeneous samples comprising different cells of different clones. I study the computational complexity of these problems and I design algorithms, based on integer-linear programming and coordinate-descent approach. On simulated data, I show that these algorithms scale on simulated instances of practical size, whereas on a prostate-cancer dataset they offer a high-resolution view of the tumor clones in term of CNAs, higher than previous analyses.

High-throughput DNA sequencing technologies are currently revolutionizing the fields of biology and medicine by elucidating the structure and function of the components of life. Modern DNA sequencing machines typically produce relatively short reads of DNA which are then assembled by software in an attempt to produce a representation of the entire genome. Due to the complex structure of all but the smallest genomes, especially the abundant presence of exact or almost exact repeats, all genome assemblers introduce errors into the final sequence and output a relatively large set of contigs instead of full-length chromosomes (a contig is a DNA sequence built from the overlaps between many reads). These problems are dramatically worse when homologous copies of the same chromosome differ substantially. Currently such genomes are usually avoided as assembly targets and, when they are not avoided, they generally produce assemblies of relatively low quality. An improved algorithm for the assembly of such data would dramatically improve our understanding of the genetics of a large class of organisms. We present a unique algorithm for the assembly of diploid genomes which have a high degree of variation between homologous chromosomes. The approach uses coverage, graph patterns and machine-learning classification to identify haplotype-specific sequences in the input reads. It then uses these haplotype-specific markers to guide an improved assembly. We validate the approach with a large experiment that isolates and elucidates the effect of single nucleotide polymorphisms (SNPs) on genome assembly more clearly than any previous study. The experiment conclusively demonstrates that the Bioluminescence heterozygous genome assembler produces dramatically longer contigs with fewer haplotype-switch errors than competing algorithms under conditions of high heterozygosity.

Nuovi ed efficienti metodi computazionali sono attualmente necessari per elaborare la ingente mole di dati generata dalle più recenti tecnologie sviluppate in svariati settori delle scienze della vita, tra cui la biologia computazionale e l’imaging medicale. In altre discipline, come la biologia dei sistemi in cui si modellano matematicamente le reti biochimiche, è necessario affrontare problemi relativi alla mancanza di dati quantitativi, e allo stesso tempo simulare efficacemente le dinamiche emergenti di queste reti. In questi contesti applicativi, le infrastrutture di calcolo ad elevate prestazioni si stanno rivelando uno strumento fondamentale per affrontare e risolvere i problemi che insorgono, in quanto permettono sia di elaborare in tempo reale ingenti quantità di dati sia di eseguire simulazioni in modo efficace ed efficiente. Durante gli ultimi anni si sta sempre di più radicando l’uso di dispositivi general-purpose caratterizzati da decine, centinaia o migliaia di core di calcolo, come ad esempio i coprocessori Many Integrated Cores e le Graphics Processing Units (GPU). L’uso delle GPU è motivato sia dalla efficienza computazionale che possono raggiungere (nell’ordine dei teraflop) grazie alle migliaia di core a disposizione sia dall’efficienza energetica che le contraddistingue. Oltre al calcolo ad elevate prestazioni, in questa tesi si sono sfruttate tecniche di intelligenza computazionale per affrontare problemi di ottimizzazione, come ad esempio la stima di parametri nella biologia dei sistemi, l’inferenza degli aplotipi nella bioinformatica, l’enhancement e la segmentazione di immagini medicali caratterizzate da istogrammi bimodali dei livelli di grigio che costituiscono le immagini stesse. La stima di parametri è stata affrontata sfruttando approcci di computazione evolutiva e di swarm intelligence insieme a nuovi simulatori accelerati su GPU - sviluppati appositamente per eseguire in parallelo sia molte simulazioni corrispondenti a diverse parametrizzazione dei modelli matematici che una singola simulazione di reti biochimiche a larga scala - permettendo di ridurre drasticamente il tempo di calcolo richiesto per calcolare le funzioni di fitness di questi approcci. Grazie alla loro efficacia nel risolvere i problemi combinatori, gli Algoritmi Genetici sono stati utilizzati per risolvere i problemi relativi alla ricostruzione degli aplotipi e l’enhancement delle immagini medicali. I due metodi proposti sono stati sviluppati sfruttando il paradigma Master-Slave che permette di distribuire il gravoso carico computazionale richiesto per risolvere questi problemi, riducendo notevolmente i tempi di calcolo. I risultati ottenuti in questa tesi mostrano come l’utilizzo del calcolo ad elevate prestazioni, unito alle tecniche di intelligenza computazionale, rappresenti una strategia efficace per la risoluzione di questi problemi, permettendo di effettuare analisi computazionali complesse richieste nelle scienze della vita.<br>Recent advances in several research fields of Life Sciences, such as Bioinformatics, Computational Biology and Medical Imaging, are generating huge amounts of data that require effective computational tools to be analyzed, while other disciplines, like Systems Biology, typically deal with mathematical models of biochemical networks, where issues related to the lack of quantitative parameters and the efficient description of the emergent dynamics must be faced. In these contexts, High-Performance Computing (HPC) infrastructures represent a fundamental means to tackle these problems, allowing for both real-time processing of data and fast simulations. In the latest years, the use of general-purpose many-core devices, such as Many Integrated Core coprocessors and Graphics Processing Units (GPUs), gained ground. The second ones, which are pervasive, relatively cheap and extremely efficient parallel many-core coprocessors capable of achieving tera-scale performance on common workstations, have been extensively exploited in the work presented in this thesis. Moreover, some of the problems described here require the application of Computational Intelligence (CI) methods. As a matter fact, the Parameter Estimation problem in Systems Biology, the Haplotype Assembly problem in Genome Analysis as well as the enhancement and segmentation of medical images characterized by a bimodal gray level intensity histogram can be viewed as optimization problems, which can be effectively addressed by relying on CI approaches. In the case of the Parameter Estimation problem, Evolutionary and Swarm Intelligence techniques were exploited and coupled with novel GPU-powered simulators-designed and developed in this thesis to execute both coarse-grained and fine-grained simulations-which were used to perform in a parallel fashion the biochemical simulations underlying the fitness functions required by these population-based approaches. The Haplotype Assembly and the enhancement of medical images problems were both addressed by means of Genetic Algorithms (GAs), which were shown to be very effective in solving combinatorial problems. Since the proposed approaches based on GAs are computationally demanding, a Master-Slave paradigm was exploited to distribute the workload, reducing the required running time. The overall results show that coupling HPC and CI techniques is advantageous to address these problems and speed up the computational analyses in these research fields.

碩士<br>國立清華大學<br>資訊工程學系<br>93<br>Single nucleotide polymorphisms (SNPs) is one of the most considered topics. This phenomenon of genetic polymorphism is the most frequent human genetic variation and corresponding to numerous applications such as medical diagnosis, drug design and phylogenis. It is also helpful for tracking disease genes. The complete sequence of SNP varieties from a single copy of chromosomes is called a haplotype. To determine haplotypes for a single individual, one alternative method proposed in [1, 2] is based on the DNA fragments and the methodology of Shotgun Sequencing Assembly. Every DNA fragment contains several SNPs information. After an appropriate assembly of the fragments, we can get the haplotypes for a single individuals. But it is difficult to get error-free fragments in the begining, how to remove errors to obtain valid assembly of all corrected fragments becomes the first problem. Since different error types are considered, two version of the problem, Minimal Fragments Removal(MFR) and Minimal SNPs Removal(MSR), were introduced in [1]. In this paper, we revised the original algorithm for MSR on fragments at most k holes. Although the original one was claimed to run in O(mn2k+2) [3], with more careful analysis, we found that it should be an O(mn2 + n2k+2) algorithm. Moreover, the existing algorithms for MFR only use the fragments from diploid genomes as input data. We extended the algorithm such that it also works robustly on the gapless fragments from polyploid genomes.

碩士<br>國立中正大學<br>資訊工程研究所<br>100<br>The genomes of most species in the biosphere is a diploid genome composed of two haplotypes. However, existing short-read assemblers for next-generation sequencing (NGS) platforms only reconstruct one consensus sequence which is a mosaic of the two haplotypes. In addition, the differences between the two haplotypes range from Single Nucleotide Polymorphisms (SNPs) to large-scale structure variations (SVs). Therefore, de novo haplotype assembly of a diploid genome is a still challenging task using NGS platforms. In this thesis, we design and implement a new framework called HapSVAssembler for de novo assembly of a diploid genome using short paired-end reads. HapSVAssembler uses a hybrid assembly approach to build a consensus sequence, identify heterozygous SNPs and SV loci, and simultaneously reconstruct the SNP/SV haplotypes via reads spanning two or more SNPs/SVs. A new optimization problem is formulated and solved by Genetic Algorithm (GA). The experimental results indicated that the assembly accuracies and continuity of HapSVAssembler is much higher than previous methods. With the ability of assembling haplotypes containing multiple types of genomic variations, HapSVAssembler is very useful for studying linkage disequilibrium across different variations.