On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems

Diplomarbeit von Sebastian Wernicke

Abstract:

This work brings together two areas of science—biology and informatics—that have only recently been connected in the emerging (and vastly growing) research field of Bioinformatics. In order to achieve a common basis for Parts 2 and 3 of this work, Part 1 intends to introduce the computer scientist to the relevant biological background and terminology (Chapter 2), and to familiarize the biologist with the relevant topics from theoretical computer science (Chapter 3).

Chapter 2 first introduces some terminology from the field of genetics, thereby defining SNPs. We then motivate the analysis of SNPs by two applications, i.e. the analysis of evolutionary development and the field of pharmacogenetics. Especially the field of pharmacogenetics is capable of having an enormous impact on medicine and the pharmaceutical industry in the near future by using SNP data to predict the efficacy of medication.

Chapter 3 gives a brief introduction to the field of computational complexity. We will see and motivate how algorithms are analyzed in theoretical computer science. This will lead to the definition of „complexity classes”, introducing the class NP which includes computationally hard problems. Some of the hard problems in the class NP can be solved efficiently using the tool of fixed-parameter tractability, introduced at the end of this chapter.

An important application of SNP data is in the analysis of the evolutionary history of species development (phylogenetic analysis – part two – chapters 4 and 5). As will be made plausible in Chapter 5 using SNP data is—in many ways—superior to previous approaches of phylogenetic analysis. In order to analyze the development of species using SNP data, an underlying model of evolution must be specified. A popular model is the so-called perfect phylogeny, but the construction of this phylogeny is a computationally hard problem when there are inconsistencies (such as read-errors or an imperfect .t to the model of perfect phylogeny) in the underlying data.

Chapter 4 analyzes the problem of „forbidden submatrix removal” which is closely connected to constructing perfect phylogenies—we will see in Chapter 5 that its computational complexity is directly related to that of constructing a perfect phylogeny from data which is partially erroneous. In this chapter, we analyze the algorithmic tractability of „forbidden submatrix removal”, characterizing cases where this problem is NP-complete (being fixed-parameter tractable in general).

Chapter 5 introduces the concept, motivation, and some known results for phylogenetic analysis. We then apply the results from Chapter 4 to perfect phylogeny problems, i.e., the problem of dealing with data-inconsistencies with respect to the underlying evolutionary model of perfect phylogeny. It will be shown that these problems are all fixed-parameter tractable and can be efficiently solved using existing algorithms.

Basically, obtaining SNP data (Part 3 – chapters 6 and 7) requires sequencing two DNA strands and comparing them to each other. The problems lie in the details: Firstly, current techniques only allow sequences of at most 500 base pairs in length to be sequenced as a whole, and secondly, it is—in terms of cost and labor—often only possible to detect the presence of SNP sites rather than being able to tell which of the two DNAs contained which base. Part 3 of this work analyzes the computational complexity of these two problems by relating them to a graph-theoretic problem4 called Graph Bipartization.

Chapter 6 introduces the computationally hard problem of Graph Bipartization, stating some known results and showing the relative hardness of the two Graph Bipartization-problem variants Edge Bipartization and Vertex Bipartization (the latter one of which is proven to be at least as hard as the former one). Following this introduction, we develop and test practical algorithms for Graph Bipartization. These algorithms—although they require a long time even for medium-sized general graphs—prove to be efficient for the Graph Bipartization problems that arise during the acquisition of SNPs, even if these graphs contain a few hundred vertices.

Chapter 7 introduces a formal definition of the computational problems of SNP analysis and proves their close relationship to Graph Bipartization. The last section of this chapter shows that the algorithms developed in Chapter 6 can be used to efficiently solve the presented problems by solving their corresponding Graph Bipartization problem. The work is concluded by Chapter 8, presenting a summary of results and suggestions for future research related to this work.

Table of Contents: