No description available.

La génomique comparative est l'étude des relations structurales et fonctionnelles entre des génomes appartenant à différentes souches ou espèces. Cette discipline offre ainsi la possibilité d'étudier et de comprendre les processus qui façonnent les génomes au cours de l'évolution. Dans le cadre de cette thèse, nous nous sommes intéressés à la génomique comparative des bactéries et plus particulièrement aux méthodes relatives à la comparaison des séquences complètes d'ADN des génomes bactériens. Ces dix dernières années, le développement d'outils informatiques permettant de comparer des génomes entiers à l'échelle de l'ADN est devenu une thématique de recherche à part entière. Actuellement, il existe de nombreux outils dédiés à cette tâche. Cependant, jusqu'à présent, la plupart des efforts ont été dirigés vers la réduction du temps de calcul et l'optimisation de la mémoire au détriment de l'évaluation de la qualité des résultats obtenus. Pour combler ce vide, nous avons travaillé sur différents problèmes statistiques soulevés par la comparaison de génomes complets bactériens. Notre travail se divise en deux axes de recherche. Dans un premier temps, nous nous sommes employés à évaluer la robustesse des alignements de génomes complets bactériens. Nous avons proposé une méthode originale fondée sur l'application de perturbations aléatoires sur les génomes comparés. Trois scores différents sont alors calculés pour estimer la robustesse des alignements de génomes à différentes échelles, allant des nucléotides aux séquences entières des génomes. Notre méthode a été expérimentée sur des données génomiques bactériennes réelles. Nos scores permettent d'identifier à la fois les alignements robustes et non robustes. Ils peuvent être employés pour corriger un alignement ou encore pour comparer plusieurs alignements obtenus à partir de différents outils. Dans un second temps, nous avons étudié le problème de la paramétrisation des outils de comparaisons de génomes entiers. En effet, la plupart des outils existants manquent à la fois de documentation et de valeurs par défaut fiables pour initialiser leurs paramètres. Conséquemment, il y a un besoin crucial de méthodes spécifiques pour aider les utilisateurs à définir des valeurs appropriées pour les paramètres de ces outils. Une grande partie des outils de comparaisons de génomes complets est fondée sur la détection des matches (mots communs exacts). Le paramètre essentiel pour ces méthodes est la longueur des matches à considérer. Au cours de cette thèse, nous avons développé deux méthodes statistiques pour estimer une valeur optimale pour la taille des matches. Notre première approche utilise un modèle de mélange de lois géométriques pour caractériser la distribution de la taille des matches obtenus lorsque l'on compare deux séquences génomiques. La deuxième approche est fondée sur une approximation de Poisson de la loi du comptage des matches entre deux chaînes de Markov. Ces méthodes statistiques nous permettent d'identifier facilement une taille optimale de matches à la fois pour des séquences simulées et pour des données génomiques réelles. Nous avons également montré que cette taille optimale dépend des caractéristiques des génomes comparés telles que leur taille, leur composition en base ou leur divergence relative. Cette thèse représente une des toutes premières études dont l'objectif est d'évaluer et d'améliorer la qualité des comparaisons des génomes complets. L'intérêt et les limites de nos différentes approches sont discutés et plusieurs perspectives d'évolution sont proposées. / Comparative genomics is the study of the structural and functional relationships between genomes belonging to different strains or species. This discipline offers great opportunities to investigate and to understand the processes that shape genomes across the evolution. In this thesis, we focused on the comparative genomics of bacteria and more precisely, on methods dedicated to the comparison of the complete DNA sequences of bacterial genomes. This last decade, the design of specific computerized methods to compare complete genomes at the DNA scale has become a subject of first concern. Now, there exist many tools and methods dedicated to this task. However, until now, most of the efforts were directed to reduce execution time and memory usage at the expense of the evaluation of the quality of the results. To fill this gap, we worked on different statistical issues related to the comparison of complete bacterial genomes. Our work was conducted into two directions. In the first one, we investigated the assessment of the robustness of complete bacterial genome alignments. We proposed an original method based on random perturbations of the compared genomes. Three different scores were derived to estimate the robustness of genome alignments at different scales, from nucleotides to the complete genome sequences. Our method was trained on bacterial genomic data. Our scores allow us to identify robust and non robust genome alignments. They can be used to correct an alignment or to compare alignments performed with different tools. Secondly, we studied the problem of the parametrization of comparison tools. Briefly, most of the existing tools suffer from a lack of information and of reliable default values to set their parameters. Consequently, there is a crucial need of methods to help users to define reliable parameter values for these tools. Most of the comparison tools are rooted on the detection of word matches. The key parameter for all these tools is the length of the matches to be considered. During this thesis, we developed two statistical methods to estimate an optimal length for these matches. Our first approach consisted in using a mixture model of geometric distributions to characterize the distribution of the length of matches retrieved from the comparison of two genomic sequences. The second approach is rooted on a Poisson approximation of the number of matches between two Markov chains. These statistical methods allow us to easily identify an optimal length for the matches from both simulated and real genomic data. We also showed that this optimal length depends on the characteristics of the compared genomes such as their length, their nucleotide composition, and their relative divergence. This thesis represents one of the earliest attempts to statistically evaluate and to improve the quality of complete genome comparisons. The interest and limitations of our different methods are discussed and some perspectives are proposed.

Passing on two-lane roadways is one of the most difficult movements a driver may perform and guidance on where passing maneuvers are prohibited is given by the location of no-passing zones. Currently the processes for identifying no-passing zone locations can be daunting and many practices require work crews to operate in the roadway creating potentially hazardous situations. Due to these challenges new alternatives need to be developed for the safe, accurate, and efficient location of nopassing zones on two-lane roadways. This thesis addresses the use of Global Positioning System (GPS) coordinates to evaluate sight distance along the vertical profile of roadways to provide an alternative for an automated no-passing zone location system. A system was developed that processes GPS coordinates and converts them into easting and northing values, smoothes inaccurate vertical elevation data, and evaluates roadway profiles for possible sight restrictions which indicate where no-passing zones should be located. The developed automated no-passing zone program shows potential in that it identifies the general location of no-passing zones as compared to existing roadway markings.; however, as concluded by the researcher, further evaluation and refinement is needed before the program can be used effectively in the field for the safe, accurate, and efficient location of no-passing zones.

Researchers use multiple sequence alignment algorithms to detect conserved regions in genetic sequences and to identify drug docking sites for drug development. In this dissertation, a novel algorithm is presented for using physicochemical properties to increase the accuracy of multiple sequence alignments. Secondary structures are also incorporated in the evaluation function. Additionally, the location of the secondary structures is assimilated into the function. Multiple properties are combined with weights, determined from prediction accuracies of protein secondary structures using artificial neural networks. A new metric, the PPD Score is developed, that captures the average change in physicochemical properties. Using the physicochemical properties and the secondary structures for multiple sequence alignment results in alignments that are more accurate, biologically relevant and useful for drug development and other medical uses. In addition to a novel multiple sequence alignment algorithm, we also propose a new protein-coding DNA reference alignment database. This database is a collection of multiple sequence alignment data sets derived from tertiary structural alignments. The primary purpose of the database is to benchmark new and existing multiple sequence alignment algorithms with DNA data. The first known comparative study of protein-coding DNA alignment accuracies is also included in this work.

No description available.

Aligning multiple biological sequences such as protein sequences or DNA/RNA sequences is a fundamental task in bioinformatics and sequence analysis. These alignments may contain invaluable information that scientists need to predict the sequences' structures, determine the evolutionary relationships between them, or discover drug-like compounds that can bind to the sequences. Unfortunately, multiple sequence alignment (MSA) is NP-Complete. In addition, the lack of a reliable scoring method makes it very hard to align the sequences reliably and to evaluate the alignment outcomes. In this dissertation, we have designed a new scoring method for use in multiple sequence alignment. Our scoring method encapsulates stereo-chemical properties of sequence residues and their substitution probabilities into a tree-structure scoring scheme. This new technique provides a reliable scoring scheme with low computational complexity. In addition to the new scoring scheme, we have designed an overlapping sequence clustering algorithm to use in our new three multiple sequence alignment algorithms. One of our alignment algorithms uses a dynamic weighted guidance tree to perform multiple sequence alignment in progressive fashion. The use of dynamic weighted tree allows errors in the early alignment stages to be corrected in the subsequence stages. Other two algorithms utilize sequence knowledge-bases and sequence consistency to produce biological meaningful sequence alignments. To improve the speed of the multiple sequence alignment, we have developed a parallel algorithm that can be deployed on reconfigurable computer models. Analytically, our parallel algorithm is the fastest progressive multiple sequence alignment algorithm.

L’évolution des protéines est un domaine important de la recherche en bioinformatique et catalyse l'intérêt de trouver des outils d'alignement qui peuvent être utilisés de manière fiable et modéliser avec précision l'évolution d'une famille de protéines. TM-Align (Zhang and Skolnick, 2005) est considéré comme l'outil idéal pour une telle tâche, en termes de rapidité et de précision. Par conséquent, dans cette étude, TM-Align a été utilisé comme point de référence pour faciliter la détection des autres outils d'alignement qui sont en mesure de préciser l'évolution des protéines. En parallèle, nous avons élargi l'actuel outil d'exploration de structures secondaires de protéines, Helix Explorer (Marrakchi, 2006), afin qu'il puisse également être utilisé comme un outil pour la modélisation de l'évolution des protéines. / Protein evolution is an important field of research in bioinformatics and catalyzes the requirement of finding alignment tools that can be used to reliably and accurately model the evolution of a protein family. TM-Align (Zhang and Skolnick, 2005) is considered to be the ideal tool for such a task, in terms of both speed and accuracy. Therefore in this study, TM-Align has been used as a point of reference to facilitate the detection of other alignment tools that are able to accurately model protein evolution. In parallel, we expand the existing protein secondary structure explorer tool, Helix Explorer (Marrakchi, 2006), so that it can also be used as a tool to model protein evolution.

L’évolution des protéines est un domaine important de la recherche en bioinformatique et catalyse l'intérêt de trouver des outils d'alignement qui peuvent être utilisés de manière fiable et modéliser avec précision l'évolution d'une famille de protéines. TM-Align (Zhang and Skolnick, 2005) est considéré comme l'outil idéal pour une telle tâche, en termes de rapidité et de précision. Par conséquent, dans cette étude, TM-Align a été utilisé comme point de référence pour faciliter la détection des autres outils d'alignement qui sont en mesure de préciser l'évolution des protéines. En parallèle, nous avons élargi l'actuel outil d'exploration de structures secondaires de protéines, Helix Explorer (Marrakchi, 2006), afin qu'il puisse également être utilisé comme un outil pour la modélisation de l'évolution des protéines. / Protein evolution is an important field of research in bioinformatics and catalyzes the requirement of finding alignment tools that can be used to reliably and accurately model the evolution of a protein family. TM-Align (Zhang and Skolnick, 2005) is considered to be the ideal tool for such a task, in terms of both speed and accuracy. Therefore in this study, TM-Align has been used as a point of reference to facilitate the detection of other alignment tools that are able to accurately model protein evolution. In parallel, we expand the existing protein secondary structure explorer tool, Helix Explorer (Marrakchi, 2006), so that it can also be used as a tool to model protein evolution.

Bioinformatics and computational biology (BCB) is a rapidly developing multidisciplinary field which encompasses a wide range of domains, including genomic sequence alignments. It is a fundamental tool in molecular biology in searching for homology between sequences. Sequence alignments are currently gaining close attention due to their great impact on the quality aspects of life such as facilitating early disease diagnosis, identifying the characteristics of a newly discovered sequence, and drug engineering. With the vast growth of genomic data, searching for a sequence homology over huge databases (often measured in gigabytes) is unable to produce results within a realistic time, hence the need for acceleration. Since the exponential increase of biological databases as a result of the human genome project (HGP), supercomputers and other parallel architectures such as the special purpose Very Large Scale Integration (VLSI) chip, Graphic Processing Unit (GPUs) and Field Programmable Gate Arrays (FPGAs) have become popular acceleration platforms. Nevertheless, there are always trade-off between area, speed, power, cost, development time and reusability when selecting an acceleration platform. FPGAs generally offer more flexibility, higher performance and lower overheads. However, they suffer from a relatively low level programming model as compared with off-the-shelf microprocessors such as standard microprocessors and GPUs. Due to the aforementioned limitations, the need has arisen for optimized FPGA core implementations which are crucial for this technology to become viable in high performance computing (HPC). This research proposes the use of state-of-the-art reprogrammable system-on-chip technology on FPGAs to accelerate three widely-used sequence alignment algorithms; the Smith-Waterman with affine gap penalty algorithm, the profile hidden Markov model (HMM) algorithm and the Basic Local Alignment Search Tool (BLAST) algorithm. The three novel aspects of this research are firstly that the algorithms are designed and implemented in hardware, with each core achieving the highest performance compared to the state-of-the-art. Secondly, an efficient scheduling strategy based on the double buffering technique is adopted into the hardware architectures. Here, when the alignment matrix computation task is overlapped with the PE configuration in a folded systolic array, the overall throughput of the core is significantly increased. This is due to the bound PE configuration time and the parallel PE configuration approach irrespective of the number of PEs in a systolic array. In addition, the use of only two configuration elements in the PE optimizes hardware resources and enables the scalability of PE systolic arrays without relying on restricted onboard memory resources. Finally, a new performance metric is devised, which facilitates the effective comparison of design performance between different FPGA devices and families. The normalized performance indicator (speed-up per area per process technology) takes out advantages of the area and lithography technology of any FPGA resulting in fairer comparisons. The cores have been designed using Verilog HDL and prototyped on the Alpha Data ADM-XRC-5LX card with the Virtex-5 XC5VLX110-3FF1153 FPGA. The implementation results show that the proposed architectures achieved giga cell updates per second (GCUPS) performances of 26.8, 29.5 and 24.2 respectively for the acceleration of the Smith-Waterman with affine gap penalty algorithm, the profile HMM algorithm and the BLAST algorithm. In terms of speed-up improvements, comparisons were made on performance of the designed cores against their corresponding software and the reported FPGA implementations. In the case of comparison with equivalent software execution, acceleration of the optimal alignment algorithm in hardware yielded an average speed-up of 269x as compared to the SSEARCH 35 software. For the profile HMM-based sequence alignment, the designed core achieved speed-up of 103x and 8.3x against the HMMER 2.0 and the latest version of HMMER (version 3.0) respectively. On the other hand, the implementation of the gapped BLAST with the two-hit method in hardware achieved a greater than tenfold speed-up compared to the latest NCBI BLAST software. In terms of comparison against other reported FPGA implementations, the proposed normalized performance indicator was used to evaluate the designed architectures fairly. The results showed that the first architecture achieved more than 50 percent improvement, while acceleration of the profile HMM sequence alignment in hardware gained a normalized speed-up of 1.34. In the case of the gapped BLAST with the two-hit method, the designed core achieved 11x speed-up after taking out advantages of the Virtex-5 FPGA. In addition, further analysis was conducted in terms of cost and power performances; it was noted that, the core achieved 0.46 MCUPS per dollar spent and 958.1 MCUPS per watt. This shows that FPGAs can be an attractive platform for high performance computation with advantages of smaller area footprint as well as represent economic ‘green’ solution compared to the other acceleration platforms. Higher throughput can be achieved by redeploying the cores on newer, bigger and faster FPGAs with minimal design effort.

Orientador: Zanoni Dias / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T22:45:38Z (GMT). No. of bitstreams: 1 Souza_MariaAngelicaLopesde_M.pdf: 2988201 bytes, checksum: 0742d490b058c7a3dae6fddd7314aba4 (MD5) Previous issue date: 2010 / Resumo: O alinhamento múltiplo dc sequências é uma tarefa de grande relevância cm Bioin-formática. Através dele é possível estudar eventos evolucionários c restrições estruturais ou funcionais, sejam de sequências de proteína, DNA ou RNA, tornando possível entender a estrutura, função c evolução dos genes que compõem um organismo. O objetivo do alinhamento múltiplo é a melhor representação do cenário dc evolução das sequencias ao longo do tempo, considerando a possibilidade dc ocorrerem diferentes eventos de mutação. Encontrar um alinhamento múltiplo dc sequencias ótimo é um problema NP-Difícil. Desta forma, diversas abordagens têm sido desenvolvidas no intuito de encontrar uma solução heurística que represente da melhor maneira possível o cenário dc evolução real, dentre elas está a abordagem progressiva. O alinhamento progressivo c uma das maneiras mais simples dc se realizar o alinhamento múltiplo, pois utiliza pouco tempo c memória computacional. Ele c realizado cm três etapas principais: determinar a distância entre as sequências que serão alinhadas, construir uma árvore guia a partir das distâncias c finalmente construir o alinhamento múltiplo. Este trabalho foi desenvolvido a partir do estudo de diferentes métodos para realizar cada etapa dc um alinhamento progressivo. Foram construídos 342 alinhadores resultantes da combinação dos métodos estudados. Os parâmetros dc entrada adequados para a maioria dos alinhadores foram determinados por estudos empíricos. Após a definição dos parâmetros adequados para cada tipo dc ahnhador, foram realizados testes com dois subconjuntos de referencia do BAliBASE. Com esses testes observamos que os melhores alinhadores foram aqueles que utilizam o agrupamento dc perfil para gerar o alinhamento múltiplo, com destaque paTa os que utilizam pontuação afim para penalizar buracos. Observamos também, que dentre os alinhadores dc agrupamento por consenso, os que utilizam função logarítmica, para penalizar buracos demonstraram melhores desempenhos / Abstract: The multiple sequence alignment is a relevant task in Bioinf'ormatics. Using this technique is possible to study evolutionary events and also structural or functional restrictions of protein, DNA, or RNA sequences. This study helps the understanding of the structure, function, and evolution of the genes that make up an organism. The multiple sequence alignment tries to achieve the best representation of a sequence evolution scenario, considering different mutation events occurrence. Finding an optimal multiple sequence alignment is a NP-Hard problem. Thus, several approaches have been developed in order to find an heuristic solution that represents the real evolution cenário, such as the progressive approach. The progressive alignment is a simple way to perform the multiple alignment, because its low memcny usage and computational time. It is performed in three main stages: (i) determining the distance between the sequences to be aligned, (ii) constructing a guide tree from the distances and finally (hi) building the multiple alignment guided by the tree. This work studied different methods for performing each step of progressive alignment and 342 aligners were built combining these methods. The input parameters suitable for most aligners were determined by empirical studies. After the parameters definition for each type of aligner, which where tested against two reference subsets of BAliBASE. The test results showed that the best aligners were those using the profile alignment to generate the multiple alignment, especially those using affine gap penalty function. In addition, this work shows that among the aligners of grouping by consensus, those that use the logarithmic gap penalty function presented better performance / Mestrado / Bioinformatica / Mestre em Ciência da Computação