Sequence analysis and structure analysis are two of the fundamental areas of bioinformatics research. This dissertation discusses, specifically, protein structure related problems including protein structure alignment and query, and genome sequence related problems including haplotype reconstruction and genome rearrangement. It first presents an algorithm for pairwise protein structure alignment that is tested with structures from the Protein Data Bank (PDB). In many cases it outperforms two other well-known algorithms, DaliLite and CE. The preliminary algorithm is a graph-theory based approach, which uses the concept of \stars" to reduce the complexity of clique-finding algorithms. The algorithm is then improved by introducing \double-center stars" in the graph and applying a self-learning strategy. The updated algorithm is tested with a much larger set of protein structures and shown to be an improvement in accuracy, especially in cases of weak similarity. A protein structure query algorithm is designed to search for similar structures in the PDB, using the improved alignment algorithm. It is compared with SSM and shows better performance with lower maximum and average Q-score for missing proteins. An interesting problem dealing with the calculation of the diameter of a 3-D sequence of points arose and its connection to the sublinear time computation is discussed. The diameter calculation of a 3-D sequence is approximated by a series of sublinear time deterministic, zero-error and bounded-error randomized algorithms and we have obtained a series of separations about the power of sublinear time computations. This dissertation also discusses two genome sequence related problems. A probabilistic model is proposed for reconstructing haplotypes from SNP matrices with incomplete and inconsistent errors. The experiments with simulated data show both high accuracy and speed, conforming to the theoretically provable e ciency and accuracy of the algorithm. Finally, a genome rearrangement problem is studied. The concept of non-breaking similarity is introduced. Approximating the exemplar non-breaking similarity to factor n1..f is proven to be NP-hard. Interestingly, for several practical cases, several polynomial time algorithms are presented.

Die räumliche Organisation des Chromatins im Zellkern ist für die Regulierung der Genexpression von großer Bedeutung. Genomische Varianten können die räumliche Organisation jedoch stören und Fehlbildungen und Krankheiten verursachen. In diploiden Genomen sind die meisten genomischen Varianten heterozygot und beeinflussen hauptsächlich das homologe Chromosom, auf dem sie sich befinden. Daher ist eine allelspezifische Analyse wichtig, erweist sich aber mit aktuellen Methoden zur Erfassung der Chromatinkonformation als äußerst schwierig. Erstens ist der Haplotyp, der die Verteilung unterschiedlicher Allele über die homologen Chromosomen beschreibt, oft unbekannt. Zweitens ist, insbesondere in Genomen mit geringer Variantendichte, wie dem menschlichen Genom, eine eindeutige Zuordnung der sequenzierten Genomabschnitte (Reads) zu ihrem Ursprungschromosom häufig nicht möglich, was die Erstellung haplotypspezifischer Chromatinkontaktmatrizen von guter Qualität verhindert. Genome Architecture Mapping (GAM) ist eine vielversprechende neue Methode mit dem Potential zur haplotypspezifischen Analyse der Chromatinkonformation. In dieser Dissertation zeige ich zunächst, dass GAM-Daten wertvolle Haplotypinformationen enthalten. Dann stelle ich GAMIBHEAR vor, einen graphenbasierten Ansatz, der die von GAM-Daten abgeleiteten Phaseninformationen nutzt, um genaue und vollständige Haplotypen zu rekonstruieren. Schließlich stelle ich Co-Phasing vor, eine neue Read-Phasing-Strategie, die erstmalig die eindeutige Zuordnung von variantenfreien Reads zu ihrem homologen Ursprungschromosom ermöglicht und somit auch die Erstellung detaillierter haplotypspezifischer Chromatinkontaktmatrizen in Maus und Mensch. Im Gegensatz zu früheren Erkenntnissen belegen meine Ergebnisse große Unterschiede in der räumlichen Organisation homologer Chromosomenkopien und ermöglichen erstmals einen sehr detaillierten Einblick in die haplotypspezifische Chromatinkonformation des menschlichen Genoms. / The spatial organization of chromatin in the nucleus plays an essential role in precise gene expression. Genomic variants can disrupt this spatial organization, potentially causing malformations and diseases. In diploid genomes, most genomic variants are heterozygous and mainly influence the homologous chromosome they reside on. Studying the effects of these variants in an allele-specific manner is crucial but has proven challenging using current state-of-the-art techniques. First, the haplotype describing the distribution of variant alleles over the homologous chromosomes is often unknown. Second, especially in genomes with a low variant density, such as the human genome, most sequencing reads map to genomic regions that are identical between homologous chromosomes, making it difficult to determine their origin. Thus, the read-phasing efficiency is insufficient to generate haplotype-specific chromatin contact matrices of good quality. Genome Architecture Mapping (GAM) is a promising new method for haplotype-specific analysis of chromatin conformation. In this thesis, I first demonstrate the ability of GAM data to provide valuable haplotype information. Then, I introduce GAMIBHEAR, a graph-based approach that leverages the GAM-derived phase information to infer accurate and complete haplotypes. Finally, building on GAMIBHEAR, I present Co-Phasing, a novel read-phasing strategy that allows for the unique assignment of variant-free reads to their homologous chromosome of origin and thus enables the creation of detailed haplotype-specific chromatin contact matrices in mouse and human. In contrast to previous findings, my results show significant differences in the spatial organization of homologous chromosomes and provide the first detailed view of haplotype-specific chromatin conformation in the human genome.