Raluca Uricaru

Associate Professor @ Bordeaux University

De novo polymorphism discovery from non-assembled NGS data

Thanks to recent technological advances, namely the Next Generation Sequencing methods, we are now able to sequence complete genomes extremely fast and at very low costs. However, the drawback of such methods is that they produce lots of short reads that need to be further on assembled. Despite the effort that has been put on developing assembly methods, assembly stays a difficult task to perform due to the short length of reads and also to the high level of redundancy.

As part of the Colib’read project, I am presently working on methods for de novo polymorphism detection directly from reads, and in particular SNPs. For this, we first build the De-Bruijn graph from the sets of reads and then we identify polymorphisms directly from the graph. This can be done based on our observation that polymorphisms correspond to particular motifs in the graph that we call bubbles. These methods can also be applied on RNA-Seq data in order to detect splicing events.

Further details in:

See the Colib’read project for more details on the tools I’ve been working on: Kissplice and discoSnp.

Genomic Sequence Comparison

A genomic sequence is generally represented by the nucleotide chain along a DNA macro-molecule. This chain can be represented as a character sequence using a four-letter alphabet : A, C, G, T. The four letters correspond to the initials of the nucleobases (Adénine, Cytosine, Guanine et Thymine) that discriminate the four types of nucleotides.

The number of base pairs composing a genome sequence varies widely from one species to another, from several thousands of nucleotides for viruses, to several hundreds of milliards for some plant species. Thanks to progresses in the domain of sequencing, several genetic sequence databases containing an annotated collection of all publicly available DNA sequences exist (e.g. GenBank).

Genomic sequence comparison is one of the most often performed computer science task by biologists. It consists in determining the level of resemblance between two or several genome sequences. It is essential for the functional annotation of genomes, the understanding of their evolution, and for phylogenetics. In particular, the conserved parts of genomes, forming the so called backbone segments, indicate the biological components common to several species or strains, while differences in sequences, variable segments, are likely responsible for what distinguishes them. Whole genome alignment (WGA) can deliver both at once.

Pairwise genome alignment

Due to the genome sizes and to the task complexity, pairwise genome alignment programs are heuristic variations on the anchor based strategy, which relies on the initial detection of similarities and their selection in an ordered chain.

The anchor based strategy operates in four phases:

We focused on the quality of pairwise bacterial genome alignment. We observed that classical alignment tools fail to align some pairs of bacterial strains. We further on investigated and we concluded that this is intrinsically due to a lack of sensitivity of the similarity detection method and, more still, to a lack of specificity of the entire strategy. Moreover, our results suggest that the sensitivity of well known methods, like MGA, Mauve or Progressive Mauve, can be greatly improved in the case of divergent genomes if one exploits spaced seeds at the detection phase.

Therefore we propose a new pairwise WGA method, YOC, and compare it with several state-of-the-art alignment tools on a large benchmark set.

Multiple genome alignment

In parallel with this pairwise WGA method, we also worked on an alternative approach to multiple genome alignment, i.e. a segmentation strategy. We implemented a tool called QOD based on this strategy capable of solving several comparative genomics problems, like new gene and homologous/orthologous gene discovery, comparison of non-assembled genomes, and most important identification of specific regions between genomes.

Further details in:

Prediction of Complex Domain Architectures in Protein Sequences

Profile Hidden Markov Models (pHMMs) are probabilistic models specially designed for the modelling of protein and domain families. They are routinely used to:

However, a majority of proteins are composed of several domains, and during evolution, events such as rearrangements or duplications may create different domain architectures in proteins of the same family. Due to their intrinsic linear structure, pHMMs cannot model several distinct domains whose number and relative order may be variable in a family.

Thus, we lack efficient tools to perform recognition and tagging in the case of complex domain architectures.

Building and Using Hidden Markov Models for Modelling Complex Multi-Domain Protein Architectures

We propose a generalized pHMM capable of modelling complex multi-domain protein architectures. Our solution, called cyclic profile HMM (cpHMM) can model the repetition of motifs or domains, as well as different relative orders between them.

A cpHMM is a HMM whose internal states are complete domains modeled by pHMMs. We provide a program for the construction of cpHMMs that takes as input pHMMs, thereby allowing the user to capitalize on already developed pHMMs (PFAM).

We adapted recognition and tagging algorithms to cpHMMs and tested them on several protein families, including the family of PentatricoPeptide Repeats (PPR).

Example of cpHMM built for the multi-domain PPR protein family:

Our results show that cpHMMs improve on pHMMs for the recognition and tagging of proteins with complex domains architectures, while keeping their efficiency. In fact, when comparing our results with the annotations of arabidopsis PPR, we show that more than 90% of the motifs are precisely recognized by the cpHMM.

Further details in:

A fully integrated domain tagging tool of all domains for a given protein is available here : cpHMM

For a ready to use cpHMM, calibrated for the PPR family, see PPR cpHMM

Event-Based Information Extraction

Large databases, storing a good proportion of the latest research results in biology and biomedicine, represent a real source of information for biologists. Medline alone, a comprehensive literature database of life sciences and biomedical information, stores more than 11 million summaries of articles.

Event-based information extraction from scientific literature databases is still a challenging task, and there is a lack of efficient and accurate systems which could retrieve and process such information. This situation is explained in principal by the absence of formal structure in the natural-language narrative in these documents.

Genic Interaction Extraction from Medline Abstracts

The extraction of interacting pairs of genes from text is one such popular extraction task. Our work in particular deals with genic interaction extraction from phrases issued from article abstracts coming from Medline database. This work was carried out as a response to the “Learning Language in Logic” Challenge task 2005 (LLL’05), which focused on applying machine learning techniques to this specific problem of Information Extraction from biomedical texts.

We see this task as a classification problem :

Further details in: