Cette thèse présente le développement, en vue de l'analyse statistique des séquences d'ADN, de nouveaux modèles permettant de prendre en compte l'hétérogénéité de ces séquences : les chaînes de Markov régulées (DMM pour drifting Markov model). Afin d'éviter l'homogénéité supposé par les modèles de Markov et de Markov cachés, nous permettons à la matrice de transition de varier du début à la fin de la séquence. A chaque position, nous avons une matrice de transition différente. Ces modèles peuvent être vus comme une alternative mais aussi comme un outil complémentaire aux modèles de Markov cachés. Nous avons considéré des dérives polynomiales ainsi que des dérives par splines polynomiales. Nous avons estimé nos modèles de multiples manières puis évalué la qualité de ces estimateurs avant de les utiliser en vue d'applications telle la recherche de mots exceptionnels. Nous avons mis en oeuvre le software DRIMM, dédié à l'estimation de nos modèles. / This document propose the conception, in the way of statistical analysis of DNA sequences, of new models which permit to take into account the heterogeneity of these sequences : the drifting Markov models (DMM). In order to avoid homogeneity of Markov models or hidden Markov models, we allow the transition matrix to vary from the beginning to the end of the sequence. At each position, we obtain a different transition matrix. DMM can be seen as a competitive model to the HMM one but it over all can be understood as a complementary tool: the hidden models of an HMM, usually fixed Markov chains can be replaced by DMM. Along this work, we consider polynomial drift or drift by polynomial splines. We estimate our models by different ways, evaluate their qualities and used them in biological applications such as the search of rare words. We develop the software DRIMM, dedicated to estimation of DMM.

L'identification des ARN non codants (ARNncs) permet d'améliorer notre compréhension de la biologie.Actuellement, les fonctions biologiques d'une grande partie des ARNncs sont connues.Mais il reste d'autre classes à découvrir.L'identification et la classification des ARNncs n'est pas une tâche triviale.Elle dépend de plusieurs types de données hétérogènes (séquence, structure secondaire, interaction avec d'autres composants biologiques, etc.) et nécessite l'utilisation de méthode appropriées.Durant cette thèse, nous avons développé des méthodes basées sur les cartes auto-organisatrice (SOM).Les SOMs nous permettent analyser et de représenter les ARNncs par une carte où la topologie des données est conservée.Nous avons proposé un nouvel algorithme de SOM qui permet d'intégrer plusieurs sources de données sous forme numérique ou sous forme complexe (représenté par des noyaux).Ce nouvel algorithm que nous appelons MSSOM calcule une SOM pour chaque source de données et les combine à l'aide d'une SOM finale.MSSOM calcule pour chaque cluster la meilleur combinaison de sources.Nous avons par ailleurs développer une variante supervisée de SOM qui s'appelle SLSOM.SLSOM classifie les classes connues à l'aide d'un perceptron multicouche et de la sortie d'une SOM.SLSOM intègre également une option de rejet qui lui permet de rejeter les prédictions incertaines et d’identifier de nouvelles classes.Ces méthodes nous ont permis de développer deux nouveaux outils bioinformatique.Le premier est l'application d'une variante de SLSOM pour la discrimination entre les ARNs codants et non-codants.Cet outil que nous appelons IRSOM a été testé sur plusieurs espèce venant de différents règnes (plantes, animales, bactéries et champignons).A l'aide de caractéristique simples, nous avons montré que IRSOM permet de séparer les ARNs codants des non-codants.De plus, avec la visualisation de SOM et l'option de rejet nous avons pu identifier les ARNs ambiguë chez l'humain.Le second s'appelle CRSOM et permet de classifier les ARNncs en différentes sous-classes.CRSOM est une combinaison de MSSOM et SLSOM et utilise deux sources de données qui sont la fréquence des k-mers de séquence et un noyau Gaussien de structure secondaire utilisant la distance d'édition.Nous avons montrer que CRSOM obtient des performances comparable à l'outil de référence (nRC) sans rejet, et de meilleur résultats avec le rejet. / The non-coding RNA (ncRNA) identification helps to improve our comprehension of biology. We know the biological functions for a majority of ncRNA classes. But, we don't know all the classes of ncRNAs. Besides, the identification of ncRNAs using computational methods is not a trivial task. The relevant features for each class of ncRNAs rely on multiple heterogeneous sources of data (sequences, secondary structure, interaction with other biological components, etc.). During this thesis, we developed methods relying on Self-Organizing Maps (SOM).The SOM is used to analyze and represent the ncRNAs by a map of clusters where the topology of the data is preserved.We proposed a new SOM version called MSSOM which can handle multiple sources of data composed of numerical data or complex data (represented by kernels). MSSOM combines data sources by using a SOM for each source and learns the weights of each source at the cluster level.We also proposed a supervised variant of SOM with rejection called SLSOM. SLSOM is able to identify and classify the known classes using multi layer perceptron and the output of a SOM.The rejection options associated to the output layer allow to reject the unreliable prediction and to identify the potential new classes.These methods lead to the development of bioinformatic tools.We applied a variant of SLSOM to the discrimination of coding and non-coding RNAs. This method called IRSOM has been evaluated on a wide range of species coming from different reigns (plants, animals, bacteria and fungi).By using a simple set of sequence features, we showed that IRSOM is able to separate the coding and non-coding RNAs efficiently.With the SOM visualization and the rejection option, we also highlighted and analyzed some ambiguous RNAs on the human. The second one is called CRSOM.CRSOM classify ncRNAs into sub classes by integrating two data sources which are the sequence k-mer frequencies and a Gaussian kernel using the edit distance. We show that CRSOM give comparable results with the reference tool (nRC) without reject and better results with the rejection option.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'alignement de séquences biologiques est une technique fondamentale en bioinformatique, et consiste à identifier des séries de caractères similaires (conservés) qui apparaissent dans le même ordre dans les deux séquences, et à inférer un ensemble de modifications (substitutions, insertions et suppressions) impliquées dans la transformation d'une séquence en l'autre. Cette technique permet de déduire, sur la base de la similarité de séquence, si deux ou plusieurs séquences biologiques sont potentiellement homologues, donc si elles partagent un ancêtre commun, permettant ainsi de mieux comprendre l'évolution des séquences. Cette thèse aborde les problèmes de comparaison de séquences dans deux cadres différents: la détection d'homologies et le séquençage à haut débit. L'objectif de ce travail est de développer des méthodes d'alignement qui peuvent apporter des solutions aux deux problèmes suivants: i) la détection d'homologies cachées entre des protéines par comparaison de séquences protéiques, lorsque la source de leur divergence sont les mutations qui changent le cadre de lecture, et ii) le mapping de reads SOLiD (séquences de di-nucléotides chevauchantes codés par des couleurs) sur un génome de référence. Dans les deux cas, la même idée générale est appliquée: comparer implicitement les séquences d'ADN pour la détection de changements qui se produisent à ce niveau, en manipulant, en pratique, d'autres représentations (séquences de protéines, séquences de codes di-nucléotides) qui fournissent des informations supplémentaires et qui aident à améliorer la recherche de similarités. Le but est de concevoir et d'appliquer des méthodes exactes et heuristiques d'alignement, ainsi que des systemes de scores, adaptés à ces scénarios. / Biological sequence alignment is a fundamental technique in bioinformatics, and consists of identifying series of similar (conserved) characters that appear in the same order in both sequences, and eventually deducing a set of modifications (substitutions, insertions and deletions) involved in the transformation of one sequence into the other. This technique allows one to infer, based on sequence similarity, if two or more biological sequences are potentially homologous, i.e. if they share a common ancestor, thus enabling the understanding of sequence evolution.This thesis addresses sequence comparison problems in two different contexts: homology detection and high throughput DNA sequencing. The goal of this work is to develop sensitive alignment methods that provide solutions to the following two problems: i) the detection of hidden protein homologies by protein sequence comparison, when the source of the divergence are frameshift mutations, and ii) mapping short SOLiD reads (sequences of overlapping di-nucleotides encoded as colors) to a reference genome. In both cases, the same general idea is applied: to implicitly compare DNA sequences for detecting changes occurring at this level, while manipulating, in practice, other representations (protein sequences, sequences of di-nucleotide codes) that provide additional information and thus help to improve the similarity search. The aim is to design and implement exact and heuristic alignment methods, along with scoring schemes, adapted to these scenarios.

L'évolution rapide dans les systèmes de communications sansfil couplée à l'utilisation de téléphones mobiles, des services satellite, de l'internet sur les réseaux sans fil et les réseaux locaux nécessitent un débit de données très élevé et une grande fiabilité. Ces débits ont augmenté rapidement dans les nouvelles applications de transmission de données de nouvelle génération. Pour répondre aux contraintes de la limitation du spectre disponible, les systèmes à porteuses multiples (OFDM), permettent une haute efficacité spectrale à cause de l'orthogonalité et un débit total s'approchant du débit de Nyquist. Par ailleurs, un système de réseaux des antennes à multi-entrées et multi-sorties (MIMO) apporte des gains importants, à la fois, pour les liens et les capacités du réseau, sans transmission de puissance supplémentaire ou sans consommation de la bande passante. La combinaison de ces deux systèmes (MIMO et OFDM) permet d’exploiter la robustesse de la liaison sur des canaux sélectifs en fréquence et sur des canaux non corrélés en espace. Une des problématiques de cette combinaison réside dans les méthodes de synchronisation. La synchronisation se divise en deux parties, la synchronisation temporelle et la synchronisation fréquentielle. La synchronisation temporelle se fait, d'une part par la synchronisation grossière qui consiste à estimer le début de chaque trame reçue, et d'autre par la synchronisation fine qui détecte le début de chaque symbole OFDM dans la trame reçue. Le principe de la synchronisation fréquentielle est de trouver le déphasage entre la fréquence à l'émission et la fréquence locale du récepteur. Dans une première partie, nous avons proposé des méthodes pour la synchronisation temporelle en se basant sur des séquences de synchronisation connues au niveau du récepteur. Nous avons réalisé une étude des différentes séquences existantes afin de comparer les efficacités de chacune de ces séquences pour la synchronisation dans un système MIMOOFDM. Dans une deuxième partie, un travail de simulation sous Matlab a été réalisé afin d'étudier les performances de nos méthodes proposées dans des canaux sélectifs en fréquence et à trajets multiples. Les résultats de simulations de ces méthodes expriment la probabilité d’acquisition de synchronisation temporelle selon le SNR. / The current wireless communication systems, mobile phones, satellite services and wireless internet networks require a very high data rate and a highly reliable degree. These rates have increased rapidly in the new applications of data transmission of new generation. To take into account the spectrum limitations, the OFDM has been proposed thanks the orthogonality between sub-carriers and the data rate that approaches to the Nyquist-Shannon sampling rate. Furthermore, the antennas technic (MIMO) can provide significant various gains, a diversity gain that improves the link reliability and the spatial multiplexing gain where different data streams are transmitted over different antennas. The combination of these two systems (MIMO and OFDM) allows to exploit the robustness of the link on the frequency-selective channels and uncorrelated channels in space. One of the issue in the combination MIO-OFDM resides on the synchronization methods. The synchronization is divided into sub parts, timing synchronization and frequency synchronization. Timing synchronization is also divided into two parts, firstly, the coarse timing synchronization is used to estimate the beginning of each received frame, and secondly, the fine timing synchronization which detects the beginning of each OFDM symbol in the received frame. The principle of the frequency synchronization is to find the shifted phase between the transmitted frequency and the local frequency at the receiver. In a first part, we have proposed different methods for timing synchronization based on synchronization sequences known at the receiver. We did a study for various existing sequences to compare the efficiencies of each of these sequences in timing synchronization for MIMO-OFDM systems. In a second part, Matlab’s simulations were conducted to study the performance of our proposed methods in multi-paths frequency-selective channels. Simulations results show the acquisition timing synchronization probability in terms of SNR.

L'exploitation de documents multimédia est en plein essor. Nous savons maintenant bien exploiter de très grandes bases d'images photographiques et y faire des recherches par le contenu efficaces. L'étape suivante consiste à se tourner vers des documents plus complexes, comme le sont les vidéos et les bandes sonores. Une des principales difficultés afférentes au traitement de tels documents vient de leur caractère temporel. Décrire de l'audio et de la vidéo revient ainsi à fabriquer des séquences de descriptions dont il est important de préserver l'ordre et l'enchaînement. Cette thèse propose deux méthodes d'indexation de documents multimédia séquentiels. La première se base sur l'utilisation de l'alignement dynamique (DTW) pour la comparaison de séquences et propose une méthode présentant des gains significatifs en termes de coût de calcul par rapport aux méthodes existantes. La seconde méthode est appliquée spécifiquement à la recherche de reprises musicales. Il s'agit d'effectuer un premier filtrage des régions temporelles susceptibles d'être mises en correspondance avec la requête, avant d'appliquer une robustification temporelle.

Streptococcus thermophilus is a low GC gram-positive bacterium massively used for the production of fermented products such as yogurt and cheeses. Every day, the dairy industry must face virulent bacteriophages and their consequences. Recently, a genetic structure called CRISPR (for Clustered Regularly Interspaced Short Palindromic Repeats) was found to be present in many bacterial and archeabacterial genomes. This system, in association with Cas (CRISPR-associated) proteins, allows the bacteria to become resistant to foreign DNA, such as phage or plasmid DNA, by the acquisition of new sequence-specific spacers. During this M. Sc. project, the transcription profile of the CRISPRl-cas system of S. thermophilus was investigated. First, the phage-sensitive wild-type strain DGCC7710 and two phage-resistant CRISPR-mutants (DGCC7710<i>2972+S4 and DGCC7710*2972+S7) were infected with the virulent phage 2972. Northern blot experiments of infected cells samples taken at time intervals were performed using a series of single-stranded 5'-labeled-probes targeting the four cas genes, the CRISPR1 locus, as well as phage genes. Phage DNA replication assays of the same samples were also done. Finally, in vitro enzymatic assays were performed using Casl and Cas2 purified proteins. In the three S. thermophilus strains tested, the four cas genes and the CRISPR1 locus were constitutively transcribed. In the phage-resistant CRISPR-mutant DGCC7710<D2972+S4 , phage mRNA specific to the acquired new spacer was rapidly degraded, whereas phage mRNAs were increasingly and strongly detected in infected phage-sensitive cells (DGCC7710). Conversely, no DNA degradation was observed. The enzymatic assays revealed that Casl and Cas2 have ssRNase activity which, in the case of Casl, is specific to a A(U)C sequence. Taken altogether, the CRISPR-cos system in S. thermophilus leads to mRNA degradation of specific phage transcripts, thereby limiting phage replication. / Streptococcus thermophilus est une bactérie utilisée pour la fabrication de produits laitiers fermentes, mais elle doit constamment lutter contre les infections par de nouveaux bacteriophages virulents. Récemment, un tout nouveau mécanisme naturel de défense contre les phages a été découvert chez S. thermophilus. Les CRISPR (clustered regularly interspaced short palindromic repeats) sont des séquences d'ADN contenant plusieurs répétitions entrecoupées de régions appelées spacers qui proviennent d'ADN extrachromosomique. Les loci CRISPR sont habituellement situés à proximité de gènes cas (CRISPR-associated). L'acquisition d'un spacer est directement reliée à une immunité contre le phage duquel provient l'ADN de ce spacer. Au cours de ce projet de maîtrise, le mode de fonctionnement du système CRISPR-cas a été étudié par analyse transcriptionnelle des gènes cas, de régions impliquées dans le locus CRISPRl-cas ainsi que des gènes viraux chez trois souches isogéniques de S. thermophilus (DGCC7710, DGCC7710[phi]2972+S4 et DGCC7710[phi]2972+S7) en cours d'infection par le phage 2972. Des travaux ont également été faits sur la replication virale chez les trois souches. Finalement, des essais enzymatiques in vitro ont été réalisés avec deux des quatre protéines Cas dont les gènes précèdent un des loci CRISPR de la souche DGCC7710. Les résultats du projet indiquent, entre autres, que les quatre gènes cas présents chez la souche S. thermophilus DGCC7710 sont transcrits constitutivement et que l'ARNm viral est dégradé par les souches résistantes ayant acquis de nouveaux spacers, ce qui ne semble pas être observé au niveau de l'ADN. Les résultats des essais enzymatiques démontrent également que les protéines Casl et Cas2 possèdent une activité sbRNase, qui dans le cas de la protéine Casl, est spécifique à la séquence A(U)C. Les résultats démontrent que le système CRISPR-cas agit de façon à dégrader l'ARN étranger comprenant une séquence identique à un spacer acquis par une souche résistante, ce qui a pour effet direct de limiter la replication du phage.

Les bactériophages sont maintenant reconnus pour jouer un rôle majeur dans divers écosystèmes. De nouveaux gènes sont fréquemment identifiés dans les génomes de ces bactériophages issus de différentes études environnementales. La majorité de ces gènes ne peuvent être associés à une fonction connue, d’où la nécessité de développer des outils génétiques performants afin mieux comprendre leur rôle dans la biologie des bactériophages virulents. Dans ce projet de maîtrise, le système CRISPR-Cas de la souche Streptococcus thermophilus DGCC7710 a été utilisé afin de pouvoir étudier des gènes sans fonction connue du bactériophage virulent 2972. Des mutations ponctuelles ainsi que de petites et de grandes délétions ont été réalisées dans le génome de phages virulents en utilisant le système CRISPR-Cas comme pression sélective. Finalement, la méthylation de l’ADN phagique a été démontrée suite à l’insertion d’un gène codant pour une méthyltransférase bactérienne dans le génome du phage 2972. / Bacteriophages are now widely recognized as major players in a wide variety of ecosystems. Novel genes are often identified in newly isolated phages as well as in environmental metavirome studies. Most of these novel viral genes have unknown functions but appear to be coding for small, non-structural proteins. To understand their biological role, very efficient genetic tools are required to modify them, especially in the genome of virulent phages. For this MSc project, specific point mutations and large deletions can be engineered in the genome of the virulent phage 2972 using the Streptococcus thermophilus CRISPR-Cas Type II-A. Furthermore, the CRISPR-Cas engineering system can be used to efficiently introduce a functional methyltransferase gene into a virulent phage genome. Finally, synthetic CRISPR bacteriophage insensitive mutants were constructed by cloning a spacer-repeat unit in a low copy vector illustrating the possibility to target multiple regions of the phage genome.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2011-2012 / Streptococcus thermophilus est une bactérie utilisée pour la fabrication industrielle de yogourts et de fromages et elle est sujette aux infections phagiques. Plusieurs mécanismes de défense contre les phages sont connus, dont le système CRISPR/Cas. Les loci CRISPR sont constitués de courtes séquences d'ADN répétées entrecoupées de séquences variables, les espaceurs. Des gènes cas et une région promotrice sont associés aux loci et la séquence homologue chez le phage est appelée le protoespaceur. Pour ce mémoire, l'effet du système CRISPRl/Cas de la souche S. thermophilus DGCC7710 sur l'ADN phagique a été étudié. Ainsi, il a été prouvé que l'ADN phagique est clivé dans les protoespaceurs par le système CRISPRl/Cas. Puis, l'analyse des différents espaceurs démontre que les motifs associés aux protoespaceurs sont plus permissifs qu'anticipé. Finalement, la méthylation de l'ADN phagique ne semble pas affecter l'immunité CRISPR/Cas ou l'acquisition d'espaceurs.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.