The advent of high-throughput sequencing and structure determination techniques has had a tremendous impact on our quest in cracking the language of life. The genomic and protein data is now being accumulated at a phenomenal rate, with the motivation of deriving insights into the function, mechanism, and evolution of the biomolecules, through analysis of their similarities, differences, and interactions. The rapid increase in the size of the biomolecular databases, however, calls for development of new computational methods for sensitive and efficient management and analysis of this information. In this thesis, we propose and implement several approaches for accurate and highly efficient comparison and retrieval of protein sequences and structures. The observation that corresponding residues in related proteins share similar inter-residue contacts is exploited in derivation of a new set of biologically sensitive metric amino acid substitution matrices, yielding accurate alignment and comparison of proteins. The metricity of these matrices has allowed efficient indexing and retrieval of both protein sequences and structures. A landmark-guided embedding of protein sequences is developed to represent subsequences in a vector space for approximate, but extremely fast spatial indexing and similarity search. Whereas protein structure comparison and search tasks were hitherto handled separately, we propose an integrated approach that serves both of these tasks and performs comparable to or better than other available methods. Our approach hinges on identification of similar residue contacts using distance-based indexing and provides the best of the both worlds: the accuracy of detailed structure alignment algorithms, at a speed comparable to that of the structure retrieval algorithms. We expect that the methods and tools developed in this study will find use in a wide range of application areas including annotation of new proteins, discovery of functional motifs, discerning evolutionary relationships among genes and species, and drug design and targeting.

Die Modifizierung von Proteinsequenzen unter anderem durch den Austausch von Aminosäuren ist ein zentraler Aspekt in evolutionären Prozessen. Solche Prozesse ereignen sich nicht nur innerhalb großer Zeiträume und resultieren in der Vielfalt des Lebens, das uns umgibt, sondern sind auch täglich beobachtbar. Diese mikroevolutionären Prozesse bilden eine Grundlage zur Immunabwehr höherer Wirbeltiere und werden durch das humorale Immunsystem organisiert. Im Zuge einer Immunantwort werden Antikörper wiederholt der Diversifizierung durch somatische Hypermutation unterworfen. Ziele dieser Arbeit waren, neue Kenntnisse über die Mikroevolution von Antikörpern während der Immunantwort zu gewinnen und die Beziehung zwischen Aminosäureaustauschen und Affinitätsänderungen zu verstehen. Zu diesem Zweck wurde zunächst gezeigt, dass die SPOT Synthese eine präzise Methode ist, um Signalintensitäten drei verschiedenen Bindungsaffinitätsklassen zuzuordnen. Antikörper-Peptid Bindungsdaten, die aus SPOT Synthese Experimenten generiert wurden, bildeten die Grundlage zur Konstruktion der Substitutionsmatrix AFFI - der ersten Substitutionsmatrix, die ausschließlich auf Bindungsaffinitätsdaten beruht. Diese bildete die Grundlage für die Gewinnung eines reduzierten Aminosäuresatzes. Durch einen theoretischen Ansatz konnte gezeigt werden, dass der reduzierte Aminosäuresatz eine optimale Basis für die Epitopsuche darstellt. Für den Prozess der somatischen Hypermutation und Selektion wurde ein neuer Ansatz präsentiert, um für die Affinitätsreifung relevante Mutationen zu identifizieren. Die Analyse zeigte, dass das Spektrum der selektierten Mutationen viel umfangreicher ist als bisher angenommen wurde. Die Tatsache, dass auch einige stille Mutationen stark bevorzugt werden, deutet darauf hin, dass entweder die intrinsische Mutabilität stark unterschätzt wurde oder, dass Selektion nicht nur auf Affinitätsreifung von Antikörpern basiert sondern auch auf ihrer Expressionsrate. / A central task of the evolutionary process is the alteration of amino acid sequences, such as the substitution of one amino acid by another. Not only do these amino acid changes occur gradually over large time scales and result in the variety of life surrounding us, but they also happen daily within an organism. Such alterations take place rapidly for the purposes of defense, which in higher vertebrates, is managed by the humoral immune system. For an effective immune response, antibodies are subjected to a micro-evolutionary process that includes multiple rounds of diversification by somatic hypermutation resulting in increased binding affinity to a particular pathogen. The goal of this work was to provide insights into the microevolution of antibodies during the immune response, including the relationship between amino acid substitutions and binding affinity changes. A preliminary step in this work was to determine the accuracy of the SPOT synthesis technique, which could be shown to be an accurate method for assigning measured signal intensities to three different binding affinity classes. A substitution matrix based on data produced with these binding experiments was constructed and named AFFI. AFFI is the first substitution matrix that is based solely on binding affinity. A theoretical approach has additionally revealed that an AFFI-derived reduced set of amino acids constitutes an optimal basis for epitope searching. For the process of somatic hypermutation and selection, a novel approach to identify mutations relevant to affinity maturation was presented. The analysis revealed that the spectrum of mutations favored by the selection process is much broader than previously thought. The fact that particular silent mutations are strongly favored indicates either that intrinsic mutability has been grossly underestimated, or that selection acts not only on antibody affinity but also on their expression rates.

The master's thesis provides a comprehensive overview of resampling methods for testing the correctness topology of the phylogenetic trees which estimate the process of phylogeny on the bases of biological sequences similarity. We focused on the possibility of errors creation in this estimate and the possibility of their removal and detection. These methods were implemented in Matlab for Bootstrapping, jackknifing, OTU jackknifing and PTP test (Permutation tail probability). The work aims to test their applicability to various biological sequences and also to assess the impact of the choice of input analysis parameters on the results of these statistical tests.

Methods for aproximate string matching of various sequences used in bioinformatics are crucial part of development in this branch. Tasks are of very large time complexity and therefore we want create a hardware platform for acceleration of these computations. Goal of this work is to design a generalized architecture based on FPGA technology, which can work with various types of sequences. Designed acceleration card will use especially dynamic algorithms like Needleman-Wunsch and Smith-Waterman.