No description available.

Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.

Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.:Mathematics and biology - having nothing in common? I. Going for a start 1. Introducing haplotyping 2. Becoming mathematical II. The MRS problem 3. The graph theoretical point of view 3.1. The MRS problem 3.2. The MRS problem on special graph classes 4. Trying to be not that bad 4.1. Greedy approaches 4.2. The local colour density 4.3. MaxNewColour 5. What is real data telling us? And the work goes on and on Bibliography

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

Haploid vererbte Polymorphismen des Y-Chromosoms sind wichtige diagnostische Werkzeuge der forensischen Genetik und verwandter Disziplinen, insbesondere der Anthropologie. Geschlechtsspezifität und uniparentaler Erbgang der Merkmale ermöglichen eine Reihe von Untersuchungen, die mit autosomalen Markern erfolglos bleiben müssen. Kurze tandem-repetitive STR-Sequenzen, die polymorphen Marker der Wahl im forensischen Labor, sind auch auf dem Y-Chromosom nachzuweisen. Aufgrund der rekombinationsfreien, paternalen Vererbung des größten Teils des Y-Chromosoms werden locus-spezifische Allele hier en bloc, als hochinformativer Haplotyp, vererbt. Die forensische Untersuchung profitiert insbesondere auf dem Gebiet der Untersuchung biologischer Spuren von der Y-chromosomalen Diagnostik: vor allem in Vergewaltigungsfällen kann die männliche DNA-Fraktion der Abstrichpräparate unabhängig von der weiblichen des Opfers untersucht und individualisiert werden. Bei der Abstammungsuntersuchung wird in solchen Fällen die Y-chromosomale Analyse empfohlen, in denen der Vater (eines männlichen Kindes) nicht zur Verfügung steht und paternale Verwandte an seiner statt untersucht werden müssen. Von den 14 evaluierten Y-chromosomalen STR-Systemen sind 9 für die forensische Praxis ausgewählt und empfohlen worden. Sie bilden den sogenannten "minimal haplotype", der heute international für die o. g. Analysen verwendet und von der zuständigen Fachgesellschaft (International Society of Forensic Genetics) in ihren Richtlinien empfohlen wird. Wegen der immensen Haplotyp-Variabilität und des uniparentalen Erbgangs ist die Frequenzbestimmung, und damit die Entscheidungsfindung für rechtsmedizinische Gutachter, nur über den Zugang zu großen Datenbanken möglich. Zu diesem Zweck wurde an der Charité die "European Y-STR Haplotype Reference Database" eingerichtet, die Frequenzabfragen auf Grundlage des aktuellen Datenmaterials online ermöglicht (http://ystr.charite.de). Aufgrund des uniparentalen Erbmodus und der im Vergleich zu Autosomen verringerten effektiven Zahl von Y-Chromosomen in der Population muß mit einem meßbaren Einfluß genetischer Drift auf die Y-STR-Haplotyp-Verteilung in der Population gerechnet werden. Mit Hilfe der AMOVA (Analysis of Molecular Variance) - Methode konnten genetische Distanzen für eine repräsentative Auswahl von über 50 weltweit verteilter Populationen berechnet werden. Der AMOVA-Test ist unentbehrlich für die Überprüfung der Eignung von Referenzdatenbanken als Grundlage der Frequenzbestimmung von Y-STR-Haplotypen. / There are a number of merits that qualify the Y chromosome as a special forensic genetic tool: the male specificity for most of its length, the absence of recombination which provides unambiguous male lineage's and the small effective population size that tends to create population specific allele distributions of the Y chromosomes. Particularly in cases of rape and other sexual assault as well as in kinship testing, Y-STR haplotyping can help to close informativity gaps. Since the main goal of forensic genetics is individualization of persons or lineages of descent an analytical strategy for the male chromosome must enable the expert to differentiate between the majority of unrelated haplotypes. For this to achieve the choice of the sequence type and its variability (i.e. its mutation rate) as well as the number of individual sequences to be used for profiling is crucial. We have introduced a STR profile for the Y-chromosome consisting of 11 microsatellite sequences which is both informative for individualization purposes as well as for a genetic distance analysis of populations. The technical simplicity of the approach led to a rapid introduction of the technique in many of the forensic labs world-wide. Intense international collaboration facilitates the generation of large haplotype reference databases, most of them are online available and searchable (Europe: http://ystr.charite.de and USA: http://www.ystr.org/usa/). By use of haplotype specific parameters such as the molecular distance (which equals the minimum number of mutational steps separating two haplotypes) and the largest available haplotype databases a Bayesian approach to evaluate Y-STR haplotype matches has been proposed. Directly inspired by our work are the recommendations of the International Society of Forensic Genetics (ISFG). These guidelines state some basic principles on forensic analysis using Y-STR polymorphisms: the use of sequenced allelic ladders, the application of a repeat-based nomenclature and the use of suitable haplotype reference databases for statistical evaluation of matches. Still a matter of research , but of the utmost interest is the potential of the Y-chromosome analysis to unravel the ethnological background of a given male profile. A dual approach - that using Y-STRs as well as Y-SNPs - probably renders the maximum amount of information about the descent of a male lineage typed in a forensic specimen.

No description available.

No description available.