Title Page

Zusammenfassung

Summary

Contents

0. Prologue 15

0.1. Evolution? 15

0.2. Toward complete genomics 16

0.2.1. Sequencing technology 16

0.2.2. Genome assemblers 17

0.2.3. Combination of sequencing technology and genome assemblers 18

0.3. Challenges 19

0.3.1. Representation of genomic datasets 19

0.3.2. Metagenomics 20

0.4. Structure 21

0.5. References 22

Chapter 1. Population Index 27

1.1. Introduction 27

1.2. Definition of "text" 28

1.3. The Suffix Array 28

1.4. The FM-index 29

1.4.1. Compressibility 29

1.4.2. Pattern Matching 31

1.5. The Population Index 32

1.6. Conclusion 33

1.7. References 33

Chapter 2. The Sequencing Error Correction 35

2.1. Introduction 35

2.2. k-mer spectrum based error correction (Trowel 1) 36

2.2.1. Overview 36

2.2.2. Trusted k-mer indexing 36

2.2.3. Error Correction 39

2.3. FM-index based error correction (Trowel 2) 42

2.3.1. Introduction 42

2.3.2. Distribution of reads 43

2.3.3. The construction of the FM-index 44

2.3.4. Error correction 44

2.4. Evaluation 45

2.4.1. Accuracy 46

2.4.2. Genome Assembly 51

2.4.3. An erroneous-base-next-to-repeats problem 53

2.4.4. Runtime and memory consumption 55

2.4.5. Sum-of-Rank table 57

2.5. Conclusion and discussion 58

2.5.1. Discussion 61

2.5.2. Conclusion 62

2.6. References 62

Chapter 3. Multiple whole genome alignment 64

3.1. Introduction 64

3.1.1. Multiple sequence alignment 64

3.1.2. Whole genome alignment 66

3.2. Method 68

3.3. Evaluation 74

3.3.1. Brief overview of known methods 74

3.3.2. Results 76

3.4. Discussion and Conclusion 82

3.5. References 83

Chapter 4. Structural variant calling 86

4.1. Introduction 86

4.2. Method 89

4.2.1. Overview 89

4.2.2. Deletions 91

4.2.3. Insertion-type events 92

4.2.4. Translocations 93

4.3. Results 94

4.3.1. Deletions 94

4.3.2. Insertions 96

4.3.3. Duplications 97

4.3.4. Inversions 98

4.3.5. Translocations 99

4.4. Discussion 100

4.5. Conclusion 101

4.6. References 102

Chapter 5. Metagenomic taxonomy classifier 104

5.1. Introduction 104

5.2. Method 105

5.3. Evaluation 107

5.3.1. Preparation 107

5.3.2. Results 109

5.4. Discussion 117

5.5. Conclusion 118

5.6. References 118

Chapter 6. Epilogue 120

6.1. References 122

Population genetics is the study of spatio-temporal genetic variants among individuals. Its purpose is to understand evolution: the change in frequency of alleles over time. The effects of these alleles are expressed on different levels of biological organization, from molecular complexes to entire organisms. Eventually, they will affect traits that can influence the survival and reproduction of organisms. Fitness is a probability of transferring alleles to subsequent generations with respect to successful survival and reproduction. Due to differential fitness, any phenotypic properties that confer beneficial effects on survival and reproduction may presumably become prevalent in a population.

Random mutations introduce new alleles in a population. The underlying changes in DNA sequences can be caused by replication errors, failures in DNA repair processes, or insertion and deletion of transposable elements. For sexual organisms, genetic recombination randomly mixes up the alleles in chromosomes, in turn, yielding a new composition of alleles though it does not change the allele frequencies. On the molecular level, mutations on a set of loci may cause a gain or loss of function resulting in totally different phenotypes, hereby influencing the survival of an organism. Despite the dominance of neutral mutations, the accumulation of small changes over time may affect the fitness, and further contribute to evolution.

The goal of this study is to provide a framework for a comparative analysis on large-scale genomic datasets, especially, of a population within a species such as the 1001 Genomes Project of Arabidopsis thaliana, the 1000 Genomes Project of humans, or metagenomics datasets. Algorithms have been developed to provide following features: 1) denoising and improving the effective coverage of raw genomic datasets (Trowel), 2) performing multiple whole genome alignments (WGAs) and detecting small variations in a population (Kairos), 3) identifying structural variants (SVs) (Apollo), and 4) classifying microorganisms in metagenomics datasets (Poseidon). The algorithms do not furnish any interpretation of raw genomic data but provide analyses as basis for biological hypotheses.

With the advances in distributed and parallel computing, many modern bioinformatics algorithms have come to utilize multi-core processing on CPUs or GPUs. Having increased computational capacity allows us to solve bigger and more complex problems. However, such hardware advances do not spontaneously give rise to the improved utilization of large-size datasets and do not bring insights by themselves to biological questions. Smart data structures and algorithms are required in order to exploit the enhanced computing power and to extract high quality information. For population genetics, an efficient representation for a pan genome and relevant formulas should be manifested. On top of such representation, sequence alignments play pivotal roles in solving biological problems such that one may calculate allele frequencies, detect rare variants, associate genotypes to phenotypes, and infer causality of certain diseases. To detect mutations in a population, the conventional alignment method is enhanced as multiple genomes are simultaneously aligned.

The number of complete genome sequences has steadily increased, but the analysis of large, complex datasets remains challenging. Next Generation Sequencing (NGS) technology is considered one of the great advances in modern biology, and has led to a dramatically more precise and detailed understanding of genomes and their activities. The contiguity and accuracy of sequencing reads have been improving so that a complete genome sequence of a single cell may become obtainable from a sequencing library in the future. Though chemical and optical engineering are main drivers to advance sequencing technology, informatics and computer engineering have significantly influenced the quality of sequences. Genomic sequencing data contain errors in forms of substitution, insertion, and deletion of nucleotides. The read length is far shorter than a given genome. These problems can be alleviated by means of error corrections and genome assemblies, leading to more accurate downstream analyses.

Short read aligners have been the key ingredient for measuring and observing genetic mutations using Illumina sequencing technology, the dominant technology in the last decade. As long reads from newer methods or assembled contigs become accessible, mapping schemes capturing long-range context, but not lingering in local matches should be devised. Parameters for short read aligners such as the number of mismatches, gap-opening and -extending penalty are not directly applicable to long read alignments. At the other end of the spectrum, whole genome aligners (WGA) attempt to solve the alignment problem in a much longer context, providing essential data for comparative studies. However, available WGA algorithms are not yet optimized concerning practical uses in population genetics due to high computing demands. Moreover, too little attention has been paid to define an ideal data format for applications in comparative genomics.

To deal with datasets representing a large population of diverse individuals, multiple sequence alignment (MSA) algorithms should be combined with WGA methods, known as multiple whole genome alignment (MWGA). Though several MWGA algorithms have been proposed, the accuracy of algorithms has not been clearly measured. In fact, known quality assessment tools have yielded highly fluctuating results dependent on the selection of organisms, and sequencing profiles. Of even more serious concern, experiments to measure the performance of MWGA methods have been only ambiguously described. In turn, it has been difficult to interpret the multiple alignment results. With known precise locations of variants from simulations and standardized statistics, I present a far more comprehensive method to measure the accuracy of a MWGA algorithm.

Metagenomics is a study of the genetic composition in a given community (often, predominantly microbial). It overcomes the limitation of having to culture each organism for genome sequencing and also provides quantitative information on the composition of a community. Though an environmental sample provides more natural genetic material, the complexity of analyses is greatly increased. The number of species can be very large and only small portions of a genome may be sampled. I provide an algorithm, Poseidon, classifying sequencing reads to taxonomy identifiers at a species resolution and helping to quantify their relative abundances in the samples. The interactions among individual bacteria in a certain population can result in both conflict and cooperation. Thus, a mixture of diverse bacteria species shows a set of functional adaptations to a particular environment. The composition of species would be changed by distinct biotic or abiotic factors, which may lead to a successive alteration in susceptibility of a host to a certain disease. In turn, basic concerns for a metagenomics study are an accurate quantification of species and deciphering their functional role in a given environment.

In summary, this work presents advanced bioinformatics methods: Trowel, Kairos, Apollo, and Poseidon. Trowel corrects sequencing errors in reads by utilizing a piece of high-quality k-mer information. Kairos aligns query sequences against multiple genomes in a population of a single species. Apollo characterizes genome-wide genetic variants from point mutations to large structural variants on top of the alignments of Kairos. Poseidon classifies metagenomics datasets to taxonomy identifiers. Though the work does not directly address any specific biological questions, it would provide preliminary materials for further downstream analyses.

집단 유전학은 개개인들 간의 시공간적인 유전적 변이들의 연구이다. 그것의 목적은 진화, 즉 시간에 따라 대립 유전자의 빈도의 변화를 이해하는 것이다. 이들 대립 유전자들의 효과는 생물학적 조직, 즉 분자 복합체로부터 전체 생물체들의 다른 단계에서 표현된다. 결국, 그들은 생물체의 생존과 생식에 영향을 미칠 수 있는 특징들에 영향을 미칠 것이다. 적합도는 성공적인 생존과 생식에 대한 이어지는 세대로 대립 유전자들을 전달하는 확률이다. 다른 적합도로 인해, 생존과 생식에 이로운 표현 형질들은 아마 개체군에 더 우위를 점할 것이다.

무작위의 변이들은 개체군에 새로운 대립 유전자들을 도입한다. DNA 서열에 일어나는 변화들은 복제 에러, DNA 교정 단계의 실패, 혹은 전이 인자의 삽입과 삭제에 의해 야기될 수 있다. 생식을 하는 생물체들에 대해서, 유전적 재조합은 염색체 상의 대립 유전자들을 무작위로 섞어서, 결국, 새로운 조합의 대립 유전자들을 생성한다. 하지만, 유전적 재조합은 대립 유전자의 빈도를 변경 시키지는 않는다. 분자 단위에서, 유전자 위치(loci)들의 집합 상의 변이들은 기능의 획득 혹은 상실을 아마 야기할 것이고, 결국 이는 완전히 다른 유전 형질을 만들게 되고, 이로 인해 한 생물체의 생존에 영향을 미치게 됩니다. 중립적인 변이들이 대다수임에도 불구하고, 시간에 따라 축적된 작은 변화들은 적합도에 영향을 미칠 것이고, 더 나아가 진화에 기여한다.

이 연구이 목적은 대용량의 유전체 데이터 집합, 가령, 1001 애기 장대 유전체 프로젝트와 같은 단일 종의 개체군 혹은 군유전체학 데이터 집합에서 비교 분석을 위한 프레임워크를 제공하는 것이다. 알고리즘들은 다음의 기능들을 제공하기 위해 개발되었다: 1) 가공되지 않은 유전체 데이터 집합의 노이즈 제거나 실효 커버리지의 개선 (Trowel), 2) 다중 전장 유전체 정렬 (WGA)를 수행하고, 개체군의 작은 변이들을 식별 (Kairos), 3) 구조 변이들(SVs)의 식별 (Apollo), 그리고 4) 군유전체 데이터에서 미생물을 분류 (Poseidon). 알고리즘은 가공되지 않은 유전체 데이터에 대한 어떠한 해석도 하지 않으나 생물학적 가설들에 대한 기초로써 분석을 제공한다.

분산과 병렬 컴퓨팅의 발전과 함께, 많은 생물정보학 알고리즘들은 CPU나 GPU 멀티코어 처리를 사용하게 되었다. 증가된 컴퓨팅 능력은 더 크고 복잡한 문제들을 해결하게 해 주었다. 하지만, 그러한 하드웨어의 발전은 대용량 데이터에 대한 더 나은 사용을 자연스럽게 가능하게 하지 않으며, 그들 자체로는 생물학적 질문들에 대한 통찰력을 주지 않는다. 개선된 컴퓨팅 파워를 이용하고, 고품질의 정보를 추출하기 위해서 똑똑한 자료 구조와 알고리즘이 요구된다. 집단 유전학에 대해서, 집단 유전체에 대한 효율적인 표현 방식과 관련된 계산식들이 도출되어야 한다. 그러한 표현 방식의 기반 위에서, 서열 정렬은 다양한 생물학적 문제들을 풀기 위해 매우 중요한 역할을 수행한다. 가령, 우리는 대립 유전자 빈도를 계산 하거나, 드문 변이를 찾거나, 유전 형질을 표현형에 매핑하거나, 특정 질병의 인과관계를 추론할 수 있다. 개체군 내의 변이들을 찾기 위해서, 기존의 정렬 기법은 개선되어 다중의 유전체가 동시에 정렬되었다.

완성된 유전체 서열들의 개수는 꾸준히 증가되어 왔지만, 대용량의 복잡한 자료 집합들을 분석하는 것은 여전히 어렵다. 차세대 염기서열(NGS) 기술은 현대 생물학에서 하나의 엄청난 발전 중 하나로 여겨지며, 유전체와 그 활동에 대해 더 정확하고 자세한 이해로 이끌었다. 염기 서열의 연속성과 정확성은 계속 개선될 것이고, 미래에 단일 세포의 완전한 유전체 서열을 얻을 수 있게 될 것이다. 화학 공학과 광공학은 시퀀싱 기술을 발전시키는 주요 기술이지만, 정보학과 컴퓨터 공학은 서열의 품질에 지대한 영향을 미쳤다. 유전체 시퀀싱 데이터는 염기의 대체, 삽입, 그리고 삭제 형태의 에러들을 포함하고 있다. 서열 길이는 주어진 유전체보다 훨씬 작다. 이런 문제들은 에러 교정, 유전체 어셈블리의 방식으로 줄어들 수 있고, 이는 더 정확한 차후 분석을 가능하게 한다.

짧은 리드 정렬기들은 Illumina 시퀀싱 기술들을 이용하여 유전적 변이들을 측정하고 확인할 때 가장 중요한 메서드이다. 새로운 긴 리드 기술이나 유전체 어셈블리를 통해 얻어진 긴 서열이 사용 가능해지면서, 더 긴 유전적 컨텍스트를 잡아낼 수 있는 정렬 기법들이 개발되어야 한다. 짧은 리드 정렬기에서 사용되는 파라미터들인 미스매치 개수, 갭 열림, 갭 확장 패널티들은 긴 리드 정렬에 바로 적용할 수 없다. 완전히 다른 관점에서, 전체 유전체 정렬기 (WGA)는 훨씬 더 긴 유전적 컨텍스트 상에서의 정렬 문제를 풀고, 비교 연구에서 기초적인 자료를 제공한다. 하지만, 기존의 WGA 알고리즘들은 높은 컴퓨팅 요구 사항 때문에 집단 유전학에서 실제적인 사용을 고려했을 때, 최적화되어 있지 않다. 더구나, 비교 유전체학에서의 응용을 위한 이상적인 자료 형태 정의에 거의 신경을 쓰지 않았다.

다양한 개개인의 커다란 개체군을 표현하는 데이터 집합을 다루기 위해서, 다중 서열 정렬(MSA) 알고리즘들이 WGA 기법들과 통합되어야 하며, 이는 다중 전체 유전체 정렬(MWGA)로 알려져 있다. 다양한 MWGA 알고리즘들이 제안되었지만, 알고리즘들의 정확도가 명확하게 측정되지 않았다. 사실, 알려진 품질 측정 도구들은 생물 개체들의 선택이나 시퀀싱 특성에 따라서 엄청나게 다른 결과들을 내놓았다. 더 심각한 문제는, MWGA 기법들의 성능을 측정하는 실험들이 오직 불분명하게 설명되었다. 결과적으로, MWGA 기법들의 정렬 결과를 해석하는 것이 어려웠다. 시뮬레이션과 표준화된(standardized) 통계를 통해 얻어진 정확한 변이의 위치를 이용하여, 단일 MWGA 기법의 정확도를 측정하는 훨씬 더 이해하기 쉬운 기법을 여기에 소개한다.

군유전체학은 주어진 생물학적 커뮤니티 (주로, 대부분 미생물)에서의 유전적 조합에 대한 연구이다. 그것은 유전체 시퀀싱을 위해서 개별적인 생물체를 길러야 하는 문제점을 극복하고, 또한 커뮤니티의 조합에 대한 양적 정보를 제공한다. 비록 환경 샘플이 더 자연스러운 유전적 물질들을 제공하지만, 분석 복합도는 훨씬 더 증가하게 된다. 종의 종류가 매우 커질 수 있고, 오직 유전체의 일부 만이 샘플링될 것이다. 나는 시퀀싱 리드를 종의 단계의 분류(taxonomy) 기호로 분류하는 Poseidon이라는 알고리즘을 제공하며, 이는 환경 샘플 상의 상대적인 빈도를 수치화하는데 도움이 된다. 특정 개체군에서 개별 미생물들 간의 관계는 상호 출돌적이거나 보완적일 수 있다. 그러므로, 다양한 미생물 종의 조합은 특정 환경에 대한 기능적 적응의 집합들을 보인다. 종의 구성은 생물학적이거나 비 생물학적인 특이적인 요소들로 인해 변경될 것이며, 이는 호스트 개체가 특정 질병에 취약하도록 만들도록 할 수 있을 것이다. 결과적으로, 군유전체 연구에 대한 기본적인 고려 사항들은 특정 종의 정확한 수치화와 주어진 환경에서 그들의 기능적 역할을 찾는 것이다.