Lade Inhalt...
Titel: On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems

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

von Sebastian Wernicke (Autor:in)
©2003 Diplomarbeit 134 Seiten
Informatik - Bioinformatik

Zusammenfassung

Inhaltsangabe: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 […]

Leseprobe

Inhaltsverzeichnis


ID 7481
Wernicke, Sebastian: On the Algorithmic Tractability of Single Nucleotide Polymorphism
(SNP) Analysis and Related Problems
Hamburg: Diplomica GmbH, 2003
Zugl.: Eberhard-Karls-Universität Tübingen, Universität, Diplomarbeit, 2003
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2003
Printed in Germany
Contents
1 Introduction
1
1.1
The Human Genome and SNPs . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Overview of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2 Biological Background and Motivation
4
2.1
Basic Genetic Terminology
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
An Introduction to SNPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Importance and Prospects of SNP Mapping . . . . . . . . . . . . . . . . . . .
8
2.3.1
SNPs in the Study of Population History . . . . . . . . . . . . . . . .
8
2.3.2
SNPs and Pharmacogenetics . . . . . . . . . . . . . . . . . . . . . . . 10
3 Computer Science Preliminaries and Notation
14
3.1
Notation for Matrices and Graphs . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2
Crash Course in Computational Complexity Theory . . . . . . . . . . . . . . 15
3.2.1
Machine-Independent Analysis . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2
Running Time--Keeping Score . . . . . . . . . . . . . . . . . . . . . . 17
3.2.3
Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3
Fixed-Parameter Tractability (FPT) . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1
An Efficient Algorithm for Vertex Cover . . . . . . . . . . . . . . . 23
3.3.2
Formal Definition and Aspects of FPT . . . . . . . . . . . . . . . . . . 26
4 Submatrix Removal Problems
29
4.1
Definitions and Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2
A Reduction to d-Hitting Set . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2.1
Finding Forbidden Submatrices . . . . . . . . . . . . . . . . . . . . . . 33
4.2.2
Approximability and Fixed-Parameter Tractability Results . . . . . . 35
4.3
Hardness Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3.1
Overview of Results--Four Theorems . . . . . . . . . . . . . . . . . . 37
4.3.2
Proofs for Theorems 4.13 and 4.14 . . . . . . . . . . . . . . . . . . . . 38
iii
CONTENTS
iv
4.3.3
Proof of Theorem 4.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.4
Proof of Theorem 4.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4
Discussion and Future Extensions . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 Perfect Phylogeny Problems
53
5.1
Phylogenetic Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.1
Introduction and Motivation . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.2
Formal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2
Perfect Phylogeny Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3
Relation to Forbidden Submatrix Problems . . . . . . . . . . . . . . . . . . . 58
5.4
Minimum Species Removal
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.5
Minimum Character Removal . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6 Graph Bipartization
67
6.1
Introduction and Known Results . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2
Reducing Edge Bipartization to Vertex Bipartization
. . . . . . . . . 70
6.3
A Branch&Bound Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.3.1
Initial Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.3.2
Data Reduction Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.4
Implementation and Comparison of the Algorithms . . . . . . . . . . . . . . . 87
6.4.1
Using the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.4.2
Some Implementation Details . . . . . . . . . . . . . . . . . . . . . . . 88
6.4.3
Tests and Test Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7 Using Graph Bipartization in SNP Analysis
96
7.1
Introduction and Overview of Results . . . . . . . . . . . . . . . . . . . . . . 96
7.2
SNP Haplotype Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.3
Inferring Haplotypes from Genotypes . . . . . . . . . . . . . . . . . . . . . . . 100
7.3.1
Minimum Genotype Removal . . . . . . . . . . . . . . . . . . . . . . . 106
7.3.2
Minimum Site Removal . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.4
Testing Branch&Bound on SNP Data . . . . . . . . . . . . . . . . . . . . . . 112
8 Conclusion
115
8.1
Summary of Results and Future Extensions . . . . . . . . . . . . . . . . . . . 115
8.2
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
List of Figures
119
Bibliography
120
Chapter 1
Introduction
1.1
The Human Genome and SNPs
Throughout its life, an individual's hereditary potentials and limits are determined by its
very own genes. Consequently, a lot of effort has been put into the Human Genome Project.
As of April 2003, 95.8% of the human genome has been sequenced in a very high quality (see
[NCBI03] for up-to-date information) and a goal has been set asking for a complete sequence
due the end of this year as more and more chromosomes become fully mapped (see, e.g.,
[Heil03]). However--quoting from [WeHu02]-- this achievement is merely the foundation
for far deeper research as
". . . we are ending the era of determining the sequence of the genetic code and
entering the beginning of the age of deciphering the biology of life underlying that
code."
Hearing that a 95.8 percentile portion of the human genome has been sequenced, one is
immediately bound to ask as to which human's genome we are actually referring to--after
all, every human has a unique genetic markup. At the beginning of the sequencing process
by the Human Genome Project, geneticists thought they would indeed have to make a choice
as to who would be chosen to provide a reference sequence of the four nucleotides A, C, G,
and T of his DNA.
1
One individual would surely constitute a "blueprint" of the human
species, the study of genetic variation among our species would however gain little insight
from this [Chak01].
The sequence we have obtained by the Human Genome Project fortunately was not obtained
through making that kind of choice: Genetic variation among humans can--in almost every
case--be traced back to variations that occur within a single nucleotide. Such a site where
there are two different nucleotides to be found in two different DNAs, is commonly referred
to as a Single Nucleotide Polymorphism (SNP, pronounced "snip") [HGSC01]. A simple
definition is given by [Ston01]:
". . . DNA is a linear combination of four nucleotides; compare two sequences,
position by position, and wherever you come across different nucleotides at the
same position, that's a SNP."
1
A thorough introduction to genetic terminology including SNPs is given in Chapter 2
1
CHAPTER 1. INTRODUCTION
2
During the Human Genome Project, 1.4 million sites of genetic variations have been mapped
[SNP01] along a reference sequence composed of hundreds of different genomes. The reason
why it was possible to combine such a multitude of different individuals' genomes into a
coherent map of the human genome lies in the fact that DNA is mostly conserved around
SNPs . The importance of SNPs is outlined e.g. in [Ston01] who refers to them as the "bread
and butter of DNA sequence variation" for they are witnesses of unique past mutations in
our genetic markup. Therefore, SNPs can give valuable hints about common evolutionary
ancestors. But there is an even more severe economic influence: As genes are widely held
responsible for the likeliness for the acquisition of certain diseases and the responsiveness
to various medical treatments, SNPs can either be made directly responsible for such a
variation or they may at least aid in the identification of the corresponding gene.
2
In this work, we shall deal with topics from the field of theoretical bioinformatics that are
connected to SNPs. Recent research [LBILS01, EHK03] has shown that all the useful appli-
cations and prospects of SNP data come at a price: Many computational problems arising
during the acquisition and application of SNP data have been proven to be computationally
"hard", meaning that they are widely believed to be impossible to solve in reasonable time .
3
However, there are techniques such as fixed-parameter tractability and data-reduction (both
to be introduced in more detail throughout this work) that allow even "hard" problems to
be solved efficiently in practical applications. This work explores the possible use of these
techniques for computationally hard problems connected to SNP analysis.
1.2
Overview of this Work
The main part of this work (Chapters 2 to 7) can be divided into three parts:
· Part 1 (Chapters 2 and 3): Introducing the Terminology
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: 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.
2
Section 2.3 gives a detailed introduction to the prospects of SNP mapping and analysis.
3
Chapter 3 introduces the topic of computational hardness in more detail.
CHAPTER 1. INTRODUCTION
3
· Part 2 (Chapters 4 and 5): Applying SNP Data (Perfect Phylogenies)
An important application of SNP data is in the analysis of the evolutionary history of
species development (phylogenetic analysis). 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 under-
lying 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 fit 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 com-
putational 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.
· Part 3 (Chapters 6 and 7): Obtaining SNP Data
Basically, obtaining SNP data 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 problem
4
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.
This work is concluded by Chapter 8, presenting a summary of results and suggestions for
future research related to this work.
4
Graphs are introduced in Chapter 3
Chapter 2
Biological Background and
Motivation
In this chapter, we establish some basic terminology from the field of genetics used through-
out this work
1
. Afterwards, we introduce SNPs and current techniques used to detect and
map them. The last section of this chapter provides an introduction to pharmacogenetics--
the area that sparked economic and scientific interest in SNPs.
2.1
Basic Genetic Terminology
All living organisms encode their genetic information in the form of deoxyribonucleic acid
(DNA, for short). DNA is a double-helix polymer where each strand is a long chain of
polymerized monomer nucleotides.
2
Basically, these are four different nucleotides; to a
deoxyribose sugar bonded with a phosphate, one of four possible bases is attached to form a
nucleotide; these possible bases include the two purines (adenine and guanine) and the two
pyrimidines (cytosine and thymine).
3
For abbreviation, the nucleotides in a strand of DNA
are denoted by the first letter of their respective base (adenine by A, guanine by G, cytosine
by C, and thymine by T). The nucleotides are joined to form a single strand of DNA by
covalently
4
bonding a phosphate of one nucleotide with the sugar of the next, a strand starts
with a sugar (this end is called the 3'-end) and ends with a phosphate (called 5'-end).
5
Two
single strands of DNA are held together by hydrogen bonds between the bases of opposing
nucleotides in the double-strand. These bonds specifically bind adenine with thymine and
cytosine with guanine. The structure of DNA is shown in Figure 2.1. Although being
1
For a more thorough introduction on genetics, see, e.g., [GMS00], [GGL02] or the chapters on genetics
in biochemistry books such as [VoVo95] or [BJS02].
2
In general, polymer designates the class of very large molecules (macromolecules) that are multiples of
simpler chemical units called monomers.
3
Actually, DNA has a lot less homogenous buildup than this because the nucleotides can be further
modified by an organism at their deoxyribose sugar. For example, bacteria use such a modification to be
able to distinguish their own DNA from foreign DNA coming, e.g., from a phage (bacterial virus). However,
such modifications will not have to concern us in this work because even in the presence of them, the basic
principles of DNA replication and translation hold.
4
A covalent bond is the interatomic linkage that results from two atoms forming a common electron
orbital.
5
The terms 3' and 5' are due to the enumeration of the carbon atoms in the deoxyribose sugar.
4
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
5
P
P
D
D
D
P
P
P
P
D
D
D
D
P
P
P
P
D
D
D
D
P
P
D
5' end
3' end
P
D
P
D
P
D
P
D
P
D
P
D
P
D
P
D
P
D
P
D
P
D
D
P
5' end
3' end
T
A
C
G
G
C
G
C
A
T
A
T
A
T
T
A
T
A
G
C
G
C
G
C
3'--ACCGATATCGGA--5'
5'--TGGCTATAGCCT--3'
Figure 2.1: Chemical structure of DNA (above) and its abbreviated notation (below). The
letters within the molecular structure above stand for phosphate (P), deoxyribose (D), ade-
nine (A), guanine (G), cytosine (C), and thymine (T). The dashed vertical lines indicate
hydrogen bonds.
just two strands of bases attached to a phosphate-sugar backbone, DNA can be extremely
long by molecular measures.
6
In order for the DNA to fit into a single cell
7
whilst still
being accessible for replication and transcription into RNA to make proteins, human DNA
is organized into very dense complexes of proteins and DNA, called chromosomes. Humans
have 22 pairs of autosomes
8
and one pair of sex chromosomes (with females carrying two
"X" chromosomes and men one "X" and one "Y" chromosome) within--almost--each cell.
The complete DNA sequence of an organism is called its genome, its genetic constitution
as a whole is called genotype
9
. Genetic areas of interest in a genome are called loci
10
. A
gene is a unit of DNA that encodes hereditary information, i.e., the sequence of all proteins
expressed by an organism, on a locus of an individual's chromosome.
11
Any one of two
or more genes that may occur alternatively at a given locus on a chromosome is called an
allele. A combination of alleles that is likely to be inherited as a whole and may be found on
one chromosome is called a haplotype. The sequence of DNA within a gene determines the
synthesis of proteins, experiments indicating that each gene is responsible for the synthesis
of one protein. Each one of the 20 proteinogenic amino acids
12
is encoded by one or more
triplets of bases. Mutations, disruptions altering the genetic information (and therefore in
most cases the corresponding protein as well), may be due to deleting, inserting, replacing,
or rearranging nucleotides in a gene; they are responsible for the unique individual genetic
markup of organisms. As already mentioned above, a human cell contains two copies of
every chromosome (excluding the gender-specific chromosomes X and Y), where one copy
is inherited from each parent. Since each parent has its unique genetic markup, equivalent
6
E.g., the diploid DNA of a human being has a total length of approximately 1.8m [VoVo95].
7
With a few exceptions, every cell in a living organism contains its whole hereditary information.
8
Autosomes are those chromosomes that control the inheritance of all characteristics except sex-linked
ones
9
The genotype of an organism is the basis for its phenotype, where phenotype denotes the two or more
distinct forms of a characteristic within a population.
10
Loci is the plural form of "locus".
11
Note that the majority of DNA is presumed not to contain any genetic information [VoVo95].
12
Proteins are basically chains of polymerized amino acids.
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
6
3'--ACAAAACTGAGCACTATTGGATCTACGACTGT --5'
SNP map
First DNA strand
Second DNA strand
3'--ACTATACTCAGCACTCTAGCATCTACGACTCT --5'
SNP sites
Figure 2.2: Mapping SNPs by comparison of two individuals' DNA sequence. Note that as
mentioned in the text, a single nucleotide variation must occur in at least 1% of a population's
individuals in order to be called "polymorphism" instead of "substitution".
genes in the two chromosomes may differ. Identical alleles on both chromosomes are referred
to as being homozygous, different alleles are denoted heterozygous.
2.2
An Introduction to SNPs
A polymorphism is a region of the genome that varies between different individuals.
13
Con-
sequently, a single nucleotide polymorphism (SNP, pronounced "Snip") is a genetic variation
caused by the change of one single nucleotide (see Figure 2.2). These variations occur quite
frequently among humans--on average, a SNP may be found approximately every 1.91 · 10
3
bases ("1.91 kilobases"), implying that over 90% of sequences longer than 20 kilobases will
contain a SNP [Chak01]. SNPs are not evenly distributed across chromosomes, most genes
contain just one or two SNPs. Currently, 93% of all genes are known to contain at least
one SNP [SNP01]. Depending on whether they are found within genes or not, SNPs are
either labeled cSNPs (coding SNPs) or ncSNPs (non-coding) SNPs. Generally, ncSNPs ap-
pear more frequently than cSNPs [Mu02]. Recall from the last section that more than one
triplet of bases may encode a certain amino acid. Often, triplets that encode the same
amino acid differ in a single nucleotide from each other. If a cSNP does not introduce an
amino acid change in the encoded protein, it is named sSNP (synonymous SNP), and nsSNP
(non-synonymous SNP) otherwise.
14
In the human genome, the ratio of sSNPs to snSNPs
is approximately one to one [Carg99].
Before outlining some prospects and the scientific as well as economic impact of SNP analysis,
we will now give a brief overview as to how SNPs are identified. In his survey on the usage
of SNPs as a tool in human genetics, Gray [GCS00] names four methods for SNP detection:
13
More precisely, a polymorphism has been defined as "the least common allele occurring in 1% or greater
of a population" [Mare97], thereby distinguishing a polymorphism from a substitution that may occur in
less than 1% of a population's individuals.
14
For example, there is an nsSNP in the gene for the HLA-H protein, where a crucial disulfide bond is
disrupted by changing the 282nd amino acid from cysteine to tyrosine, causing a metabolic disorder known
as hereditary hemochromatosis [PSS97].
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
7
· Identification of single strand conformation polymorphisms (SSCPs): In this technique,
DNA fragments of a locus containing the presumed SNP are amplified (e.g., multiplied
into many identical fragments) using PCR amplification.
15
These fragments are then
put on a polyacrylamide gel to which a current of diluting liquid is applied. Due to
different folding of DNA fragments with different sequences, the speed of fragments
will differ if they contain SNPs. The presence of SNPs may afterwards be confirmed
by sequencing the respective patterns. This method is widely deprecated because of
its low throughput and sometimes poor detection rate of about 70%.
· Heteroduplex Analysis: During PCR amplification of an individual that is heterozy-
gous for a SNP, a heteroduplex
16
may be formed between two strands that are com-
plementary to each other with exception of the SNP site. These heteroduplexes can
then be detected either as a gel band (analogously to SSCP detection) or using high-
performance liquid chromatography (HPLC). This SNP detection method combines
reasonable throughput rates of 10 minutes per sample with a high detection rate be-
tween 95% and 100%.
· Direct DNA sequencing: This is the currently favored high-throughput method for
detecting SNPs. According to [Carg99], almost a million base pairs can be analyzed
in 48 hours with detection rates for heterozygotes ranging between 95% (using cheap
"dye-terminator sequencing") and 100% (using a more expensive and laborious method
known as "dye-primer sequencing"). Dye-terminator sequencing has been used by the
SNP Consortium [Hold02] which published over 1.4 million SNPs in human DNA
[SNP01]. Comparing equal loci in different versions of high-quality DNA sequences
has recently led to an increase of in silico detection of SNPs.
· Variant detector arrays (VDAs): In this technique, glass chips with arrays of oligonu-
cleotides are used to bind specific sequences derived in PCR amplification. VDA has
a quality comparable to dye-terminator sequencing and is especially useful in rapidly
scanning large amounts of DNA sequence.
17
It should also be stressed that for SNP detection, an appropriate set of alleles from which
SNPs are to be inferred needs to be chosen, as the different alleles occur with quite different
frequencies in different populations (such as human ethnic groups).
In Chapter 7, we will be concerned with the algorithmic tractability of two problems that
arise during the identification of SNPs: First, the sequencing of chromosomes in order to
obtain haplotypes has to deal with some errors in the reading and assembling process of the
DNA sequences (this will be discussed in more detail in Chapter 7). Second, haplotypes
are--due to prohibitively high cost and labor--seldomly identified by sequencing single
chromosomes. Rather, genotype information (both copies of a chromosome) is obtained,
from which haplotypes can be inferred under certain assumptions. We will see in Chapter 7
that both problems are closely related (in a certain way even equivalent) to a problem called
"graph bipartization" for which we will develop efficient algorithms in Chapter 6.
15
The polymerase chain reaction (PCR, for short) can quickly and accurately make numerous identical
copies of a specific DNA fragment. A PCR machine is capable of producing billions of copies of a DNA
fragment in just a few hours. PCR is a widely used technique in diagnosing genetic diseases, detecting low
levels of viral infection and for genetic fingerprinting in forensic medicine.
16
A heteroduplex may either be a piece of DNA in which the two strands are different, or it is the product
of annealing a piece of mRNA and the corresponding DNA strand.
17
SNP identification through arrays is a rapidly growing market responsible for the recent development
of biotechnology companies such as Affymetrix, Applied Biosystems, Marligen Biosciences, and Orchid
Biosciences, among many others.
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
8
2.3
Importance and Prospects of SNP Mapping
SNPs are mainly useful for two areas of research: the study of population history (e.g.,
see [BBNE03]) and--an area of great economical significance--pharmacogenetics (e.g., see
[Rose00]). In this section, we will introduce both applications. The algorithmic tractability
of some problems in the study of population history using SNPs is dealt with in Chapter 5.
2.3.1
SNPs in the Study of Population History
SNPs often are a basis for various studies of population history (e.g., see [Tish96], [Tish00],
and [Mu02]). Historically, such studies employed gene trees of non-recombining loci inherited
from one parent such as mitochondrial DNA or the Y chromosome [Avis94]. A disadvantage
of this approach is that such loci are subject to a lot of stochastic parameters, which in
turn caused the requirement of vast amounts of loci to be analyzed to gain confidence over
the results. The preference for SNPs as genetic markers arose from this problem, as SNPs
provide a broad range of unlinked nuclear genetic markers and are thus able to capture "a
genome-wide picture of population history" [Niel00]. Furthermore, SNPs are advantageous
over previous methods such as using microsatellites
18
for population history studies because
they show a very favorable mutation pattern and greatly simplify the task of unbiased
sampling of genetic variation [BBNE03]:
· Mutation pattern: Microsatellites have a mutation rate of 10
-4
per generation as
opposed to the rate of 10
-8
displayed by SNPs. This makes multiple mutations for a
single SNP unlikely, therefore only two alleles exist of most SNPs. Such a property
greatly facilitates populational analysis--e.g., we will make use of it in the algorithmic
inference of haplotypes from genotypes in Chapter 7. Furthermore, mutations in SNPs
are more evenly distributed than in microsatellites, where the mutation rate is often
hard to estimate [BBNE03].
· Unbiased Sampling: Due to their uniform mutation rates, SNPs may be selected at
random in populational studies, avoiding previous bias that arose due to the fact that
often, only loci with well known mutation rates would be chosen for analysis. Fur-
thermore, [BBNE03] suggests that cross-species analysis of SNPs can provide greater
insight into the natural occurring rate of genome-wide variation than biased loci such
as microsatellites.
SNPs have been of great interest in populational studies due to the phenomenon that often
there is a collection of SNP sites where the individual SNPs are not independent of each
other; rather, a phenomenon called linkage disequilibrium is observed.
19
This phenomenon
refers to the fact that often, haplotype combinations of alleles at different loci are correlated
in their appearance frequency, forming a so-called linkage disequilibrium block (LD block)
[DRSHL01]. The size of LD blocks is often debated and ranges from size suggestions of a few
kilobases (in empirical research [Dunn00] and computer simulation experiments [Krug99])
to more than a hundred thousand kilobases [Abec01]. Independent of the discussed size, the
presence of linkage disequilibrium is believed to reflect the fact that haplotypes descended
18
Microsatellites are stretches of DNA consisting of tandem repeats of a small, simple sequence of nu-
cleotides, e.g., GCTGCTGCT. . . GCT. Often in literature, microsatellites are also referred to simple tandem
repeats (STRs).
19
For the human genome, linkage disequilibrium was studied, e.g., in [Reic01].
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
9
"populational bottleneck"
population narrows
e.g., by selection process
States of first, fifth and seventh SNP site correlate due to
the respective common ancestral haplotype
SNP maps for the individuals of a large initial population:
states of different SNP sites show no correlation
population redevelops
from bottleneck haplotypes
Figure 2.3: Development of linkage disequilibria in SNP sites: An initial, genetically diverse
population is drastically reduced in its number of individuals (e.g., by selection processes
in a unique environment). This causes a "populational bottleneck" where only a very few
different haplotypes remain within a population. Redevelopment of a population based on
this non-diverse genetic material causes linkage disequilibrium in the alleles, which decays
over time due to mutations and recombination.
from common ancestral chromosomes; linkage disequilibrium may therefore also be an in-
dicator for populational bottlenecks
20
[Mu02]. The phenomenon of linkage disequilibrium
relating to SNPs is illustrated in Figure 2.3.
Linkage disequilibrium of individuals' genes within a population "decays" with population
history due to recombination [HaCl97]. It is believed that linkage disequilibrium around
common alleles is a lot less frequent than around rare alleles, which are generally younger
and thus less decayed by recombination [Watt77]. Using these assumptions, Reich et al.
[Reic01] have shown that they can relate some linkage disequilibria to events such as the
last glacial maximum 30 000-15 000 years ago, migration patterns in ancient Europe, or
the dispersal of anatomically modern humans in Africa. The article mentions that for some
20
A populational bottleneck is a period in population history where there are very few individuals in
the population. These individuals then gave rise to the haplotypes found in a population today--conserved
genetic patterns in the haplotypes can therefore be backwardly related to the respective ancestral individuals
that lived during the bottleneck.
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
10
populations not as large as Europeans ([Reic01] mentions Yorubans as an example), the
resolution of their linkage disequilibrium blocks is too coarse, but nevertheless--referring to
studies such as [Tish96], [Tish00], or [Mate01]--" [. . . ] simultaneous assessment [of linkage
disequilibria] at multiple regions of the genome provides an approach for studying history
with potentially greater sensitivity to certain aspects of history than traditional methods
[. . . ]" [Reic01]
Additionally to being able to gain deep biological insights into species development and
population history, the study of linkage disequilibria and the search for common ancestors
of species might also have high economical and health political impact. One example for this
is the recent study of the malaria parasite Plasmodium Falciparum in [Mu02], this parasite
has been of intense interest since it infects hundreds of millions of people each year, being
responsible for almost 3 million annual deaths [Brem01].
21
An effective vaccine against
malaria, for example, must trigger an immune response that is equivalent or superior to
the one gained by contact with natural antigens. By finding some common SNP regions in
different Plasmodium Falciparum populations, it is the hope of current research to build an
accurate map of the ancestral relationship of various Plasmodium Falciparum strains. Such a
map of ancestral relationships could help in identifying common antigens for immunizations
[Gard98].
It was conjectured in [RLHA98] that the human malaria parasite experienced a populational
bottleneck about 5000 years ago, further sparking the hope that it would be possible to find
some common drug targets among malaria parasites. Although an extensive study of SNPs
on the Plasmodium Falciparum genome carried out by Mu et al. [Mu02] have shown that
this is probably not the case and Plasmodium Falciparum is rather a "quite ancient and
diverse" population (with the most recent common ancestor being a few hundred thousand
years old), it is still hoped that some more recent common ancestors of different strains can
be found in order to obtain an assay of promising drug targets and vaccines:
"For the first time, a wealth of information is available [. . . ] that comprise the
life cycle of the malaria parasite, providing abundant opportunities for the study
of [the . . . ] complex interactions that result in disease." [Gard98]
Although the genetic sequence and the insights gained by SNPs alone are no cure for malaria
and other widespread diseases, they seem to be a promising start.
The study of populational history based on traits of individuals (which--among others--may
be the presence of highly correlated SNP sites) and its algorithmic tractability is studied in
Chapter 5 of this work, where a special model of analysis called perfect phylogeny will be
employed. As will be seen in Chapter 5, SNPs provide very good data for this model due to
their very low mutation rate.
2.3.2
SNPs and Pharmacogenetics
The understanding of SNPs is believed to be a key to the research area known as pharmaco-
genetics. Using SNPs in pharmacogenetics is of immense economical interest to pharmaceu-
tical companies. It has led to the founding and funding (hundreds of millions of US dollars)
of the SNP Consortium [Hold02], a joint effort of major pharmaceutical companies such as
Bayer, Bristol-Myers Squibb, Glaxo Wellcome, Aventis, Novartis, Pfizer, Roche, SmithKline
21
2001-2010 has been named the "Malaria Rollback Decade" by the WHO [WHO03] to emphasize efforts
being made in limiting the widespread of malaria.
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
11
Beecham, and Zeneca. Interdisciplinary connections of the SNP Consortium include IBM
and Motorola.
The problem with a lot of drug therapies is the possibility of adverse drug reactions by
patients: Research by Lazarou, Pomeranz, and Corey [LPC98] suggests that, in 1994, such
reactions were responsible for millions of hospitalizations and almost a hundred thousand
deaths. This value is not likely to have improved lately and is hindering the introduction of
new medications that are effective in most patients but pose unbearable risks: For example,
the quite effective anticonvulsant drug Lamictal
c
by Glaxo Wellcome is only reluctantly
prescribed because of a potentially fatal skin rash that arises as a side effect in five percent
of all patients taking the drug [Maso99]. The problem of the different effects drugs exert
on patients has long been known and studied, already over a hundred years ago Sir William
Osler
22
reflected:
"If it were not for the great variability among individuals, medicine might as well
be a science and not an art." (as cited by [Rose00])
Pharmacogenetics is an area of research that studies how genetic variation influences a
patients responsiveness and responses to drugs (a good introduction to pharmacogenetics
is, e.g., [Rose00]), thereby trying to give physicians the possibility of using objective data
about a patient's likeliness to react to prescribed drugs in a predictive way. The basic idea in
pharmacogenetics is to build a profile of an individual's genetic variations in order to predict
effectiveness and side-effects of drugs. As was discussed above--since genetic variation is
mainly due to SNPs--a hope of pharmacogenetics relies on building an accurate map of
SNP haplotypes.
Roughly speaking, the hope is to identify linkage disequilibrium loci around certain genes
that are susceptible for causing a certain adverse reaction to drugs. The same technique has
already been applied in the study of individuals' susceptibility to certain complex genetic
diseases such as Alzheimer's disease: In an analysis of polymorphisms on the ApoE gene
locus on chromosome 19, Martin et al. [Mart00] reported the detection of those SNPs
in linkage equilibrium that are associated with Alzheimer's disease. A number of other
studies successfully related the susceptibility for complex genetic diseases such as migraine
with aura, psoriasis, and insulin-independent diabetes mellitus to certain SNPs in linkage
disequilibrium [Rose00]. Now, just as linkage disequilibria can be related to the susceptibility
for diseases, they can also be related to certain drug reactions. Two good examples for this
are, e.g., patient's reactions to nortriptyline and beta-2-agonists:
· Nortriptyline is a medication against depression which is converted to an inactive
compound within the body by drug metabolizing enzymes called the cytochrome P450
enzymes. Specifically, an enzyme labeled CYP2D6 is a key in inactivating nortryptiline
and removing the inactivated substance from the body--except in some people that
have variations in their CYP2D6 encoding gene. These variations may lead to two
undesired effects [DeVa94]: People referred to as "ultra metabolizers" have a variation
that causes the synthesis of too much CYP2D6 in their body, thus inactivating so
much nortriptyline that these people are likely to receive insufficient antidepressant
effects from nortriptyline. A more dangerous variation is found in people referred to
as "poor metabolizers" who do not synthesize sufficient amounts of CYP2D6--these
22
Osler, Sir William, Baronet (*1849, 1919). Canadian physician and professor of medicine who played a
key role in the transformation of the curriculum of medical education in the late 19th and early 20th century.
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
12
SNP genotype profile of
patients in clinical trial
medicine effective?
ineffective
effective
effective vs. ineffective
SNP genotype profile of
predictors for efficacy
SNP profile for prediction
"effective"
SNP profile for prediction
"ineffective"
Figure 2.4: Profiling SNPs in pharmacogenetics: If there is a section of the SNP genotype
profile that proves to be different in patients where a drug is effective as opposed to patients
where a drug shows no efficacy or undesired side-effects, this region can be used to predict the
effectiveness and potential risks due to side effects in a patient before a drug is prescribed.
are likely to experience toxic side effects due to accumulation of nortriptyline in their
body. Genetic testing for variation in the gene for the CYP2D6 enzyme could avoid
both scenarios.
· Beta-2-antagonists such as albuterol are important to the treatment of asthma. In-
teracting with the beta-2-adrenergic receptors in the lung, they cause the freeing of
airways by inducing muscle relaxation in the lung muscles. A SNP in the gene encoding
the beta-2-adrenergic receptor causes the carriers of one SNP variant to express fewer
of these receptors, therefore receiving little relief of asthma symptoms upon a standard
dose of albuterol [Ligg97]. Testing for presence of the specified SNP in patients can
allow to clearly identify those 45% in the North American population
23
who can only
poorly control their asthma by beta-2-antagonists.
It is clear that the prospects of being able to predict the efficacy of a drug whilst minimizing
the risk of side-effects is of great interest to the pharmaceutical industry, which could then--
as Roses proposes in [Rose00]--create efficacy profiles for patients (see Figure 2.4) already in
phase II
24
clinical trials of medication. Abbreviated SNP profiles
25
could be used to record
23
This figure should be similar for Europeans.
24
Clinical trials are divided into five steps: Preclinical Research includes controlled experiments using a
new substance in animals and test tubes and may take several years. Phase I trials are first tests of the
investigated drug on humans. Doses are gradually increased to ensure safety. Phase II trials will gather
information about the actual efficacy of a drug. Phase III trials studies a drugs effects with respect to
gender, age, race, etc. A successful phase III trial leads to the admission of a drug to the public market.
Occasionally, phase IV trials are conducted that are--in principle--phase III trials on an even broader
variety of patients.
CHAPTER 2. BIOLOGICAL BACKGROUND AND MOTIVATION
13
adverse reactions in patients and thus be able to predetect even the most rare adverse events.
Furthermore, the development of new, more effective drugs can be facilitated: The parallel
developments of drugs targeting specific symptoms is facilitated because patients who do not
respond to a certain medication can be profiled in early clinical trial stages. Additionally,
the development of medications which are highly effective in only a comparably small part
of a population (e.g., a medication with 30% response rate) become profitable as they may
be specifically prescribed to patients to whom the respective substance will be effective.
Pharmacogenetics relying on SNP linkage analysis seems to be a promising start to replacing
trial-and-error prescriptions with specifically targeted medical therapies.
25
Abbreviated SNP profiles contain only the SNP information of a patient that is relevant for a drug
efficacy prediction. The introduction of abbreviated profiles plays an important role in the discussion about
the fear of "individual DNA profiling" because they cannot be backwardly related to a patient.
Chapter 3
Computer Science Preliminaries
and Notation
The first section of this chapter introduces the notation used throughout this work, followed
by a brief introduction to those ideas in computational complexity that are important to this
work. Especially, the last section focuses on fixed-parameter tractability, laying a foundation
for the computational complexity analysis in the following chapters.
3.1
Notation for Matrices and Graphs
Matrices. By an n × m matrix A we are referring to a rectangular arrangement of n · m
elements into n rows and m columns. By a
ij
we designate the element in A that may be
found at the jth position of the ith row. We will use the terms A and (a
ij
) synonymously.
Graphs. A graph consists of vertices and edges, where a vertex is an object with a name
and other properties (such as a color) and an edge is the connection of two vertices. We
will denote a graph G with n vertices and m edges by (V, E) where V = {v
1
, . . . , v
n
}
and E = {e
1
, . . . , e
m
} V × V . In this work, only simple, undirected graphs are considered,
meaning
· a vertex cannot be connected to itself by an edge,
· no two vertices may be connected by more than one edge, and
· an edge leading from a vertex u to a vertex w also leads from w to u.
By the term subgraph G = (V , E ) we are referring to a graph with V V and E =
E
(V × V ). Given a set V , G = (V , E ) with E = E (V × V ) is called the subgraph
induced by V in G.
A vertex v is said to have degree d--denoted by degree(v) = d--if there are exactly d edges
in G that are adjacent to v.
A path p of length in a graph G = (V, E) is a sequence of + 1 distinct vertices v
1
v
2
. . . v
+1
in G such that for each 1 i , v
i
and v
i
+1
are connected by an edge. A cycle of
length
in G is a sequence of
vertices v
1
v
2
. . . v v
1
in G such that v
1
. . . v
is a path in G
14
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
15
and {v , v
1
} E. We call G = (V, E) a tree if it contains no cycles; a tree containing a
specially designated node
1
--called the root of the tree--is called rooted. Nodes of degree 1 in
a rooted tree are called leafs. A graph G = (V, E) is called connected if any two vertices u, v
V
are connected by a path in G. A subgraph of G that is maximally connected with respect
to its number of vertices is called a connected component.
A graph G = (V, E) is called bipartite if we can divide the set V of vertices into two
disjoint subsets V
1
and V
2
such that E contains neither edges between vertices in V
1
nor
edges between vertices in V
2
. The graph G is called planar if it can be embedded into an
(Euclidian) plane without any intersecting edges.
In this work--especially in Chapter 6--we will be using the following set of operations on
graphs:
· Subgraph removal. Let V V be a subgraph of G = (V, E). By G \ V we will
denote the subgraph that is induced in G by V \ V .
· Vertex deletion. Let u be a vertex in a graph G = (V, E). By G \ {u}, we denote
the graph that is induced in G by V \ {u}.
· Edge deletion. Let e be an edge in a graph G = (V, E). By G \ {e}, we denote the
graph G = (V, E ) with E = E \ {e}.
A vertex separator in a graph G = (V, E) is a set V V of vertices in G such that G \ V is
not connected. If |V| = k, we call V a vertex separator of order k. The definition of an edge
separator E E of order k is analogous.
3.2
Crash Course in Computational Complexity Theory
Generally speaking, "an algorithm is a procedure to accomplish a specific task. It is the
idea behind any computer program" [Skie98]. The first goal for any algorithm is to be
effective, i.e. providing correct solutions to a given problem, however, an effective algorithm
is of little use if it is not efficient, i.e., requires more resources (especially time) to solve a
problem than can be provided. Computational complexity theory deals with the amount
of resources--the two most important of which are time and memory
2
--required to solve
a certain computational problem by an algorithm. A brief introduction to analyzing the
time complexity of algorithms is given in [Skie98], a very thorough treatment of complexity
theory may be found, e.g., in [Papa94]. This section will introduce some basic terminology
from computational complexity theory that will be used throughout this work.
3.2.1
Machine-Independent Analysis
Imagine that we are given an algorithm called A (in any programming language) that solves
a certain problem P when given an input I, called an instance of P. We would now like to
analyze the performance--especially concerning speed--of this algorithm. The most obvious
way of this would be to run A on a lot of instances of P and measure the time it takes for A
1
In order to distinguish tree from graphs more easily throughout this work, we will use the term "vertex"
for general graphs and the synonymous "node" for vertices in trees.
2
Since only the notion of time complexity is important for this work, we shall omit space complexity in
the following introduction.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
16
to complete its task each time. However, with this approach, we quickly run into a multitude
of problems, the most crucial of which are that the absolute time measured is influenced
by the actual machines computer architecture
3
, absolute time values are only useful for one
particular type of machine, we can seldomly test the algorithm on all conceivable instances,
and a purely practical analysis provides no indication about an algorithm's maximal (worst-
case) running time.
Complexity theory tries to avoid these problems arising from a direct machine analysis by
analyzing computational problems in a more formal and mathematical way. This analysis
is machine-independent whilst still trying to incorporate the fundamental workings of a
modern computer. Traditionally, complexity theory relies on the Turing Machine as its
model of computation which is, however, a quite abstract model of computation lacking
any close relationship to modern computers.
4
For this work, we do not require the many
special features offered by Turing Machines and shall therefore rely on another model of
computation that is sufficiently precise for our analysis, far more intuitive and more closely
related to a "real" computer than a Turing Machine.
5
This model is the RAM model of
computation, which Skiena [Skie98] describes quite vividly as a computer
"where each `simple' operation (+,-,*,=,IF,call) takes exactly 1 time step [and]
loops and subroutines are not considered simple operations. Instead, they are
the composition of many single-step operations. . . . Each memory access takes
exactly one time step, and we have as much memory as we need."
Using this model, the computational time of an algorithm is given by simply counting the
number of time steps it takes the RAM machine to execute it on a given problem instance.
The advantage of the RAM model lies in the fact that it captures the essential behavior of
a modern computer without introducing any fickle parameters such as memory bandwidth,
actual processor speed, and memory access time, just to name a few. The next subsection
demonstrates the usage of this model in the analysis of an algorithm's time complexity.
This, however, requires a last step of formalization: Besides the machine model, the term
"problem" needs to be specified.
6
Computational problems may be stated in many ways, the most important of which--at least
in the context of this work--are decision problems (the output can be just either "Yes" or
"No") and optimization problems (the output is a solution which is minimal/maximal in
some respect). Most of computational complexity theory solely deals with decision problems
because almost any "reasonable" way of stating a problem can be transformed into a decision
problem.
7
Although a whole branch of theoretical informatics--computability--has evolved
concerning the existence of decision problems that are undecidable (i.e., not algorithmically
3
A modern computer's performance is, e.g., influenced by its processor, memory bandwidth, techniques
such as pipelining and caching, the operating system, the programming language and its compiler, etc. Due
to these many factors it is sometimes even difficult to obtain consistent results on a single, defined machine.
4
There are many reasons why Turing Machines are nevertheless used in computational complexity theory:
For example, requirements such as memory and time are very easy to define for a Turing Machine and can
be analyzed with great accuracy. Furthermore, Turing Machines can simulate other machine models--one
Turing Machine can, in theory, even simulate an infinite number of Turing Machines. The simulation of
an algorithm on the RAM model (which will be introduced shortly) by a Turing Machine requires only
polynomially more time than its execution on directly on the RAM (the term "polynomially more time" will
also be defined more precisely later on in this chapter).
5
A quite thorough analysis of different machine models can be found in Chapter 2 of [Papa94].
6
An algorithm is by definition already given in a formal fashion.
7
E.g., instead of asking "What are all prime numbers between 0 and 280581?" we can solve the decision
problems "Is 1 a prime?" ("No"), "Is 2 a prime?" ("Yes"), . . . , "Is 280580 a prime?" ("No") separately.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
17
solvable) by computers, we can assume for this work that we are always given decidable
decision problems.
Analyzing decision problems is closely related to the fact that in complexity theory, a pro-
blem is generally formulated as a language L and asking (i.e., deciding by an algorithm)
whether a given instance I is part of that language. Both the language L and the instance I
are a subset of
for an alphabet , where is a finite set of symbols and
is the set of
all words that may be generated by concatenation of symbols from , including the empty
word
which contains no symbols at all.
8
Expressing a given problem as a language is--in
most practical cases--quite straightforward.
9
For this work, the computational complexity
for solving a problem can be seen as equivalent to the complexity of answering the cor-
responding decidability question. It should be noted that stating a problem in form of a
language presents this particular problem in a very abstract form. Neither an algorithm for
solving the problem is given nor any obvious hint about the time complexity of solving this
problem. In order to deal with this, we will introduce the model of complexity classes and
reductions later on in this chapter.
For the sake of simplifying the discussion in this work, we will refrain from stating problems
in the form of a language. Instead, we will simply assume that the given problems may be
stated in the form of a language. Furthermore, instead of asking whether an instance I is
in L, we shall directly deal the object x that I represents (such as a word, number, graph,
etc.)
10
. We then call x an instance of the problem P = "I L?".
3.2.2
Running Time--Keeping Score
We discussed at the beginning of the last subsection that, given an algorithm for a problem P,
knowing how this algorithm performs on certain instances x of P is of little use. Rather,
in order to understand the quality of an algorithm, it is vital to know how it performs on
any conceivable instance x of P and express this performance in an intuitive way. This
is done by introducing three new ideas: Analyzing how the running time of algorithms
scales with the problem size, distinguishing between worst, best and average-case complexity
(emphasizing on worst-case complexity), and analyzing the scaling of the algorithm in its
asymptotic behavior.
The first idea is based on the intuitive observation that an algorithm should generally take
longer time to run as the presented instance becomes larger. For instance, a graph problem
on a general
11
graph consisting of ten vertices should be easier to solve than the same
problem for a general graph with a thousand vertices. Therefore, if x is an instance of a
problem P, the running time t of an algorithm is expressed as a mathematical function f
8
For example, if = {0, 1},
= { , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, . . . }.
9
E.g., the problem of deciding whether a given number is a prime number would have to be expressed
as L
prime
= {p {0, 1}
| p is the binary representation of a prime number} (with = {0, 1}) and then
asking "given I
, is I L
prime
?".
10
We shall assume for this work that such a representation, i.e, the encoding of x as I is always a valid
one, meaning we do not need to worry about any cases where I does not encode a valid object x.
11
By "general" we mean that the given graph has no special properties that greatly simplify the solution
of the respective problem.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
18
x
x
f
(x)
c
· g(x)
x
x
f
(x)
c
· g(x)
x
x
f
(x)
c
2
· g(x)
c
1
· g(x)
f
(x) = O(g(x))
f
(x) = (g(x))
f
(x) = (g(x))
Figure 3.1: A function f (x) and its bounds in O-notation: From left to right, g(x) is an
upper, lower and tight bound on f (x). Note how the respective bounding property of g only
needs to be true for all x > x .
of n := |x|, the size of x:
12
t
algorithm
(x) = f (|x|) = f (n)
Given a fixed size n for the input instance x and an algorithm A that runs with x as an
input, we distinguish between the best-case, average-case, and worst-case running time:
t
best
(A, n) =
min
x
: |x|=n
t
A
(x), t
avg
(A, n) =
x
: |x|=n
t
A
(x)
|{x | |x| = n}|
,
and t
worst
(A, n) =
max
x
: |x|=n
t
A
(x).
Most of the time, only the worst-case complexity of an algorithm is interesting since average-
case and--especially--best-case complexity provide no information whatsoever about the
running time that A might have when presented with any instance x. E.g., for average-
time complexity the problem here lies in the definition of "average": There may be some
problems which are rather easy to solve on many instances, but this is of no use if we
should--consciously or not--be dealing just with hard instances during the application of the
algorithm.
13
Albeit open to criticism about being too pessimistic, the worst-case complexity
of an algorithm seems to be the most useful measure for its performance.
The computational RAM model introduced in the last subsection provided a way to measure
the running time of a given algorithm A exact to a single time unit. This degree of accuracy
is not useful as for such exact counts the function f that measures the running time of A will
often get very complicated and unintuitive to analyze.
14
Moreover, as we are interested in
the performance of an algorithm on a real-world machine and not on the hypothetical RAM,
measuring the running time of A down to the last time unit finds no application. Therefore,
12
Later on, we will analyze algorithms in more detail using various parameters of the input. For example,
the running time of a graph algorithm may depend on the number of edges as well as on the number of
vertices in the graph. The number of edges in the graph is lower than |V |
2
, but explicitly using the number
of edges provides a better analysis. In order to simplify the discussion, however, we will for now assume that
there is just a single input size parameter given.
13
Moreover, the corresponding mathematical analysis of average-case complexity even for simple algo-
rithms and a clear definition of "average case" is often highly involved and complicated.
14
Moreover, there are often trivial steps depending on the notation of the algorithm (such as initialization
of variables) that require just a little constant amount of time and are thus not interesting for a general
performance-analysis.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
19
computational complexity theory, instead of directly analyzing f , rather analyzes the upper
and lower bounds of f using the O-Notation (pronounced "Big Oh Notation"):
Definition 3.1 (O-Notation):
Given two functions f :
R
>
0
R
>
0
and g :
R
>
0
R
>
0
. We will say that
· f = O(g) if there exist a constant c
R and an x R such that for all x > x , f(x)
c
· g(x) (g is an upper bound for f ).
· f = (g) if there exist a constant c
R and an x R such that for all x > x , f(x)
c
· g(x) (g is a lower bound for f ).
· f = (g) if there exist two constants c
1
, c
2
R with c
1
c
2
and an x
R such that
for all x > x , c
1
· g(x) f (x) c
2
· g(x) (g is a tight bound for f ).
This notation is illustrated by Figure 3.1.
15
Analogously to preferring the worst-case complexity over the best- and average-case com-
plexities when analyzing the performance of an algorithm, it is common practice to provide
an upper bound for an algorithm's running time instead of a lower or tight one.
16
To provide an example on how to determine the running time of an algorithm and express it
in O-Notation, we will now analyze an algorithm for a well-known problem in computational
complexity, called Vertex Cover.
Definition 3.2 (Vertex Cover)
Input: A graph G = (V, E) and a parameter k.
Question: Is it possible to choose a set V V with |V | k such that every edge in E has
at least one endpoint in V ?
In Figure 3.2, a graph and one of its vertex covers is given in order to illustrate this definition.
A very trivial algorithm A
VCtrivial
for this would be to simply try all possible solutions of
size k and see whether one of these hypothetical solutions is indeed a vertex cover for the
given graph:
Algorithm: Trivial algorithm A
VCtrivial
for Vertex Cover
Input: A graph G = (V, E) with V = {v
1
, . . . , v
n
}
Output: "Yes" if G has a vertex cover of size k, "No" otherwise
01
for every k-sized subset V of V do
02
if V is a vertex cover for G
03
return "Yes"
04
return "No"
15
For a concrete example, consider the function f (x) = x
4
+ x
2
+ x - ln x + 1234. If x 6, we have
f
(x) = x
4
+ x
2
+ x - ln x + 1234 < x
4
+ x
2
+ x - ln x + 6
4
<
5 · x
4
=: 5 · g(x),
f
(x) = x
4
+ x
2
+ x - ln x + 1234 > x
4
>
1 · x
3
=: 1 · g(x), and
1 · g(x) := 1 · x
4
< f
(x) = x
4
+ x
2
- ln x + 1234 < 5 · x
4
= 5 · g(x)
and therefore f (x) = O(x
4
), f (x) = (x
3
), and f (x) = (x
4
).
16
This is mainly due to the fact that tight bounds on the running time of algorithms are often neither
intuitive nor easy to grasp mathematically.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
20
A Vertex Cover for G
A graph G = (V, E)
(black vertices)
Figure 3.2: A graph G = (V, E) and a vertex cover of size 17 (black vertices) for G. Note
how for each edge in G, at least one of its endpoints is in the given vertex cover. The shown
vertex cover for G is optimal in the sense that there is no vertex cover for G with fewer than
17 vertices (this was verified using a computer program).
We will now analyze the running time of A
VCtrivial
in terms of the number of vertices (|V |)
and the number of edges (|E|) in G.
17
Let us start with lines
03
and
04
: Since both
terminate A
VCtrivial
, they are executed at most once, and thus do not play a role in the
asymptotic running time of A
VCtrivial
. Line
02
can be executed by calling the following
subroutine: Iterate over all edges of G, and check for every edge whether at least one of its
endpoints is in V . If we have been clever enough and marked those vertices that are in V
during the execution of line
01
, executing this line only requires O(|E|) running time. For the
seemingly most difficult line to analyze, line
01
, we make use of the machine-independency
of our analysis by using an algorithm for generating subsets from the extensive available
literature on algorithms (e.g., [CLRS01], [Knut97]).
18
In [Knut03], we can find an algorithm
that generates all k-sized subsets V of V in
O
(
|V |
k
) = O
|V |!
k
!(|V | - k)!
= O
1
k
!
|V | · (|V | - 1) · · · (|V | - k + 1)
k factors
=O(|V|
k
)
time on a RAM-like machine. For finding the total running time of A
VCtrivial
, it is now
sufficient to observe that line
01
causes line
02
to be executed once for each of the at most
|V |
k
subsets generated. Taking into account the time requirements of line
02
, the total running
17
A quick glance at the algorithm demonstrates the advantage of all the conventions we have introduced
above. E.g., if we were not to use the O-Notation for the worst-case bound we are about to determine, we
would explicitly have to look at the exact number of steps a RAM needs to generate a subset in line 01, to
store G, to determine whether V is a vertex cover of G, and so on.
18
Note that the RAM models in literature do not necessarily need to be defined precisely the way we
have. E.g., in the RAM model used in [Knut97], some computing steps take more than one unit of time.
However, this is not important for the performance of an algorithm in O-notation: Assume, for example,
that each simple computational operation would consume four time units instead of one on a machine RAM
as opposed to our RAM model. If there is an algorithm that, e.g., requires O(n
3
) time on the RAM, it
would require O((4n)
3
) = O(64n
3
) = O(n
3
) time on the RAM .
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
21
time for A
VCtrivial
is therefore bounded by
O
(|V |
k
· |E|).
This upper bound is quite unsatisfactory for practical applications, for it implies an enormous
worst-case running time even for small graphs and small k.
19
Note that from the discussion
so far, it is not clear wether this is due to a poorly designed algorithm we have come up with
or it is a result of some "inherent complexity" of Vertex Cover. The next subsection and
the following section will demonstrate that actually both is true, that is, Vertex Cover
is believed to be "hard to solve" (we will define this more precisely in the next subsection)
but there are ways of "taming" this inherent complexity, as will be shown in Section 3.3.
3.2.3
Complexity Classes
In the previous subsection, we have given an algorithm to solve Vertex Cover that was
quite impractical for large input graphs. However, it was not clear whether this problem is
hard to solve in general or if we just haven't come up with a good algorithm. We would
now like to know wether there is a better algorithm for Vertex Cover than the one
presented, or--even better--know the fastest possible algorithm for Vertex Cover (i.e.,
the minimum time complexity of Vertex Cover). The first request is comparably easy to
come by, we just have to look for an algorithm with a better worst-case running time than
the one presented. The latter however is a lot harder to deal with, because in finding a lower
bound for the time complexity of Vertex Cover it is necessary to consider every thinkable
algorithm for Vertex Cover--even algorithms that have not yet been found.
20
However,
there is another way to approach the problem of complexity bounds using reductions and
complexity classes.
Reductions will allow us to divide problems into different "classes of difficulty". The idea
behind this is the following: Although not knowing how hard an individual problem might
be, we can relate problems to each other so that we know they are both "equally hard" to
solve, meaning if there is a fast algorithm for one problem, there must be one for the other
problem, too. A collection of such related problems is called a complexity class (a more
formal definition will follow shortly). Problems are grouped together in complexity classes
by finding a computationally "cheap"
21
transformation between instances of one problem
and the other. Then, loosely speaking, if we know that if one of the two problems turns out
to be easy to solve, we also know that the second problem is easy to solve, because we can
apply the algorithm for the easy problem to transformed instances of the other one. In a
more formal fashion:
Definition 3.3 (Polynomial Time Reduction):
Given two languages L
1
1
and L
2
2
. We call L
1
1
polynomial-time reducible
to L
2
2
(designated L
1
poly
L
2
) if there is a function R from
1
to
2
that can be
computed in polynomial time on any x
1
and
x
L
1
R(x) L
2
.
19
For example, finding out if a graph with 75 vertices and 200 edges has a vertex cover of size 10 would
require c · 10
21
steps on our RAM where c is some constant 1 omitted on the O-notation.
20
Except for a few very rare cases of problems (such as sorting), the question of lower complexity bounds
therefore generally remains unanswered.
21
In our context, this will imply a polynomial running time with respect to the original instance's size.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
22
In complexity theory, there are a lot of more specialized reductions, some of which we will
get to know in Section 3.3, that are more "delicate" in the sense that they impose stricter
requirements on R than just being computable in polynomial time. However, we shall work
just with polynomial time reductions for the rest of this section.
The concept of polynomial time reduction may be used to build a hierarchy of computational
problems. This hierarchy consists of classes C. In each class, we can find those problems that
are solvable using the resources allowed by the respective class. Furthermore, we introduce
the concept of completeness to identify those problems in a class that are computationally
as hard to solve as any other problem in that class. In this way, if a problem that is complete
for a class should prove to be "easy" to solve, we know the same to be true for all other
problems that are in C.
Definition 3.4 (Complexity Class Hardness and Completeness):
Let C be a complexity class. A language L is called C-hard if all languages in C can be
reduced in polynomial time to L. We call L C-complete, if L is C-hard and in C.
There is a vast number of complexity classes known today (see, for example, [Aaro03]), each
of them grouping together problems with various properties. Two of the first classes that
were developed and are of much interest for this work are P and NP.
Definition 3.5 (P and NP):
The complexity class P is the class of computational problems that can be solved in polyno-
mial time on a deterministic Turing Machine.
The complexity class NP is the class of computational problems that can be solved in poly-
nomial time on a nondeterministic Turing Machine.
Although our definition uses the term "polynomial" to describe all problems in NP, it
is widely believed that all NP-complete problems are only solvable in exponential time.
The reason for this is the computational model underlying the definition: A nondetermin-
istic Turing Machine is a very unrealistic model of computation, being able to--vaguely
speaking--correctly "guess" the solution to a problem and then only needing to verify its
correctness (the process of checking must then be done in polynomial time). However, all
computers known today are deterministic, and therefore they have to "emulate" the guessing
steps of the nondeterministic Turing Machine in order to find a solution to an NP-complete
problem. This emulation is done by simply checking all possibilities for a possible solution
which takes--in worst-case complexity--an exponential amount of time.
It must be stressed that no proof whatsoever has been given that problems in NP are at
best solvable in exponential time. All we have stated is a plausibility argument: There are
thousands of problems known to be NP-complete (even the rather outdated list of [GaJo79]
lists hundreds of NP-complete problems), finding a polynomial time algorithm for just one
NP-complete problem would show that all NP-complete problems are polynomially solvable,
but this has not happened in spite of over 25 years of research so far. There are therefore
two important things to be remembered throughout this work:
· When saying that a problem is harder than another one, we are always referring to
relative complexity bounds, i.e., we are saying that if a "harder" problem should turn
out to be efficiently solvable, so will the easier problem (but not vice-versa).
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
23
· Sometimes we will use an argument such as ". . . --since this would imply that P = NP"
in our proofs, which is based on the unlikeliness of P = NP. It would, however, be
more correct--albeit unusual--to write "Unless P = NP, the following holds true:
. . . ".
The Vertex Cover problem posed at the beginning of the previous subsection has been
proven to be NP-complete in [GaJo79], where it is shown that Vertex Cover is even NP-
complete for planar graphs where each vertex has a degree of at most 3
22
. A long time, an
NP-completeness proof for a problem was taken as a synonym for "unsolvable already for
moderate input sizes" (coining the term "intractable"). However, this is not true in general,
as the next section demonstrates.
3.3
Fixed-Parameter Tractability (FPT)
We have seen in the previous section how algorithms can be analyzed machine-independently
by observing how they scale with the size of their respective input. This size we named n. We
have also seen the class NP, reasoning that problems complete for this class most probably
have a worst-case running time that is exponential, i.e., an NP-complete problem can only
be solved in
(a
n
)
time for some a > 1. Since this usually implies unreasonably high running times for large n,
problems that are NP-hard are also referred to as being intractable. We have also stated
in the last section--citing from [GaJo79]--that the problem Vertex Cover (see Defini-
tion 3.2) is NP-complete. The NP-completeness of Vertex Cover implies that it is most
probably only solvable in O(a
n
) time where n is the size of the input instance and a is some
constant. However, this definition provides us with two loopholes:
· We have made no statement about the size of a. A small a could lead to algorithms
that are fast enough even for a fairly large n.
· We have made no good use of the fact that--besides the size of the input graph--any
instance of Vertex Cover contains a parameter k that might be restricted to a small
value. What if we could restrict the exponential complexity of Vertex Cover to the
parameter k which is given along with the input graph according to Definition 3.2 ?
It might seem at first that observing these two "loopholes" is just splitting hairs in an
imprecise definition, but in this section, we shall use exactly them to develop a more efficient
algorithm for Vertex Cover than the trivial O(|V |
k
· |E|) algorithm used as an example
for complexity analysis in the last section. After that, a short introduction to parameterized
complexity theory is given.
3.3.1
An Efficient Algorithm for Vertex Cover
At the end of this section, we will have improved the O(|V |
k
· |E|) algorithm for Vertex
Cover given in the previous section to an O(2
k
· |E|) algorithm. The strategy for this will
be quite straightforward.
22
Recall the definitions of "planar" and "degree" from Section 3.1.
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
24
Recall Definition 3.2. If a given graph G has a vertex cover of size k, then we can choose k
vertices in G such that every edge in G includes at least one vertex from the cover. This
means, if we were to search for a vertex cover V for G we can simply pick any edge e =
{v
a
, v
b
} in G, and then, knowing that either v
a
or v
b
must be in the vertex cover, consider
two distinct cases for V : Either V contains v
a
or V contains v
b
. For each of these cases,
we would then look at the uncovered edges, pick one, and again consider the two cases for
putting a vertex of that edge into V (the common term for this is to branch into those two
cases). This recursive algorithm leads to a tree-like structure searching for vertex covers of
size k for G--depicted in Figure 3.3--that is commonly referred to as a search tree. Note
that for each level down the search tree, we have one vertex less left to form a vertex cover
for G. If we cannot find a vertex cover for G in the kth level of the search tree, then, as we
have tried all possibilities of a vertex cover for G, G has no vertex cover of size k.
The described algorithm can be rewritten in a more formal fashion:
Algorithm: search tree algorithm A
tree
for Vertex Cover
Input: A graph G = (V, E) with V = {v
1
, . . . , v
n
} and a parameter k
Output: "Yes" if G has a vertex cover of size k, "No" otherwise
01
if G contains no edges then
02
return "Yes"
03
if G contains edges and k = 0 then
04
return "No"
05
pick an edge e = {v
a
, v
b
} from G
06
V
a
V \ {v
a
}
07
E
a
E \ {e E | v
a
is an endpoint of e}
08
if
A
tree
with G
a
:= (V
a
, E
a
) and k - 1 as inputs returns "Yes" then
09
return "Yes"
10
V
b
V \ {v
b
}
11
E
b
E \ {e E | v
b
is an endpoint of e}
12
if
A
tree
with G
b
:= (V
b
, E
b
) and k - 1 as inputs returns "Yes" then
13
return "Yes"
14
return "No"
This algorithm is illustrated in Figure 3.3. So what is the running time of this algorithm?
Without the recursion (i.e., calling A
tree
as a subprocedure), A
tree
would require O(|E|)
time to generate G
a
and G
b
, since each edge must be looked at to see if it is adjacent to v
a
or v
b
, respectively (we shall assume that deleting a vertex from G takes constant time). The
algorithm A
tree
calls A
tree
(with a different input, especially, k is decreased by one) at most
two times. Each of those calls again calls A
tree
at most two times, and so on, until the
algorithm is called with k = 0. This means, in a worst-case analysis, A
tree
is called
2
initial k
· 2
k
-1
· 2
k
-2
· · ·
2
k
-k+1
·
1
k
-k=0
= 2
k
times. Each call itself takes--as mentioned above--O(|E|) time which means in total, A
tree
requires at most
O
(2
k
|E|)
time to solve a given instance (G, k) of Vertex Cover, a fairly large improvement compared
to the trivial algorithm proposed in the last section, and moreover, the exponential part in
the running time of A
tree
is independent of the size of G. This makes Vertex Cover a
CHAPTER 3. COMPUTER SCIENCE PRELIMINARIES AND NOTATION
25
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
initial k
k
- 1
k
- 2
k
- 3
a
b
c
d
e
f
g
h
i
j
i
h
a
e
d
c
h
g
a
b
a
e
j
f
Figure 3.3: The search tree for finding a vertex cover of size k for a given graph: Given
the graph G and a parameter k > 3, the above figure demonstrates how a search tree
algorithm would try to find a vertex cover of size k for G. In each node of the search tree,
an edge e = {u, v} that is not yet covered is chosen from G (designated by coloring the
adjacent vertices of e grey) and the algorithm branches into two cases: Either, u is in the
vertex cover or v. The respective vertex from G is chosen into the vertex cover (and can
then, along with its adjacent edges which are now covered, be removed from G), k decreased,
and the algorithm proceeds if no vertex cover for G has been found yet and we have not yet
chosen k vertices into the cover.
fixed-parameter tractable problem, because, as long as k is constant, the time required to
solve Vertex Cover on (G, k) using A
tree
is polynomial (for Vertex Cover, even linear)
with respect to the size of the input graph G.
Note that A
tree
is not the optimal fixed-parameter algorithm for Vertex Cover known to-
day. In [CKJ01] and [NiRo03
b
], O(1.29
k
)-algorithms for solving Vertex Cover are given.
This is done by optimizing the search tree: Instead of branching into two subcases and
decreasing k by one each time the algorithm is called recursively, the algorithm may branch
into more complex cases, allowing it to decrease k by more than 1 in some branches of
the tree. Using the mathematical tool of recursion analysis, it can be analyzed how these
complex cases decrease the base of the exponent in the algorithm. It should furthermore
be noted that the algorithm uses the technique of problem kernel reduction
23
on Vertex
23
Kernel reductions are based on the idea that using the parameter k, we can already decide for some
parts of the input instance how they will add to the solution of the problem. A problem kernel reduction
causes the input instance to be smaller than f (k) for some f whilst being computable in polynomial time.

Details

Seiten
Erscheinungsform
Originalausgabe
Jahr
2003
ISBN (eBook)
9783832474812
ISBN (Paperback)
9783838674810
Dateigröße
1.5 MB
Sprache
Englisch
Institution / Hochschule
Eberhard-Karls-Universität Tübingen – Informatik 17, Wilhelm-Schickard-Institut für Informatik
Erscheinungsdatum
2014 (April)
Note
1,0
Schlagworte
human genom phylogen graph haplotyp

Autor

Zurück

Titel: On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems
book preview page numper 1
book preview page numper 2
book preview page numper 3
book preview page numper 4
book preview page numper 5
book preview page numper 6
book preview page numper 7
book preview page numper 8
book preview page numper 9
book preview page numper 10
book preview page numper 11
book preview page numper 12
book preview page numper 13
book preview page numper 14
book preview page numper 15
book preview page numper 16
book preview page numper 17
book preview page numper 18
book preview page numper 19
book preview page numper 20
book preview page numper 21
book preview page numper 22
book preview page numper 23
book preview page numper 24
book preview page numper 25
book preview page numper 26
book preview page numper 27
book preview page numper 28
134 Seiten
Cookie-Einstellungen