The research conducted in CoBalt takes its source in many areas in biology or bio-informatics and from biological
data: genomic and protein sequences, RNA, biological interaction networks, metabolic and signaling pathways. We aim at
the development of new algorithms and formal models for the analysis of genomes, networks, and more generally the study
of complex systems. We ultimately support biologists in their understanding of the structure and the history of genomes.
We thus address challenges initiated from problems in bioinformatics while encompassing issues in computer science:
algorithmic recognition and inference patterns, data mining and classification, modeling of complex dynamical systems,
prediction and comparison of networks, comparative genomics in a broad sense. Our activities are twofold as detailed in
the following paragraphs.
Coding, processing and analysis of biological data
A common denominator of the work carried by members of CoBalt is the exploitation and analysis of biological data,
tackled from different angles. A first concern is the transformation of data obtained from new sequencing technologies
(NGS) into assembled biological sequences, with the assembly quality as a key factor for the exploitation of results.
Mix contributes to this problem and offers a method relying on the computation of a graph capturing how genome segments
have been pieced together. We also considered the simultaneous use of data from multiple metagenomics agencies to improve
a taxonomic assignment algorithm (through a collaboration with a team from Barcelona).
The annotation of genomic data can be tackled by either combining various bioinformatics approaches to infer protein
function or simultaneously process multiple genomes. To this end, we have developed a management and annotation system of
genomic data (MAGUS – http://magus.gforge.inria.fr/).
YAGA (Yeast Genome Annotation Automatic) is a pipelined process performing automatic annotation through the
implementation of a ab initio predictor and a combiner. YAGA has been successfully used on genomes of bacteria of the genus
Oenococcus. Comparative genome and transcriptome analysis of these bacteria revealed the existence of common and
stem-specific gene repertoires for the stress response in relation to adaptation to the ecological niche (wine, cider).
The prediction of pseudogenes improves quality annotation bacterial genomes. Other ad hoc approaches have been attempted
to study the plasticity of interesting genomes. Tsvetok (for “Scaling out data and calculations”) is a prototype
application based on a NoSQL schema and implementing the MapReduce paradigm to reach scalability when performing
comparative genomics computations.
The identification of protein families is commonly accomplished using classification/clustering algorithms, a
longstanding research issue in our team. Because NGS produce much larger amounts of data, these approaches must be
revisited. We proposed extended and more scalable version of algorithms separating orthologs from paralogs. In the context
of a clade of bacterial genomes, we analyzed the impact of ad hoc substitution matrices taking into account the
compositional bias of these genomes with the aim of improving the prediction of peer relationships. To understand the
organization of contemporary genomes, one solution is to reconstruct ancestral states that lead to modern living
organisms. We proposed a new method to identify common markers for evolutionarily distant species. We applied the
comparative maps and reconstructed a new method for the reconstruction of ancestral architectures based on adjacencies
between calculated markers and genomic distances between genomes. These algorithms have enabled the ancestral
reconstruction for yeast clade Hemiascomycetes.
Another aspect of our work is the development of algorithmic methods for analyzing biological structures with a
special focus on RNA data. The molecular function of these biological entities closely relate to their spatial
conformations, thus requiring to analyze both their nucleotide sequence and the inter-nucleotide linkages called
secondary structure. Chaining techniques on trees inspired from the BLAST and FASTA methods have been designed to
address this problem, leading to an optimal chaining algorithm (as part of a collaboration with C. Chauve from SFU,
Canada). Another example result in this area is the introduction of filtering strategies for fast searching of noncoding
RNA applied to genome annotation (as part of L. Bourgeade’s PhD). The team has also been a key player in the development
of a benchmark approach for RNA comparison algorithms (ANR Brasero project, see http://brasero.labri.fr)
The BioRica framework orchestrates our efforts and results to analyze and study biological processes by complex systems
based on hierarchical modeling of cell behavior. We furthermore build hybrid approaches combining multiple formalisms to
cover different aspects of cell behavior (available from dedicated databases). Our approach has been validated by modeling
two systems: the kinetics of fermentation of wine and the decision of cell differentiation in the adipocyte and osteocyte
path. Each system contains several models that are under the control of “switches” using coefficients. These theoretical
developments have enabled us to gain international visibility and thus be involved in the development of international
standards regarding the reproducibility of in silico simulations of biological systems.
We proposed the first global metabolic model of the oleaginous yeast Yarrowia lipolytica (annotated by the Genolevures
consortium) by applying our software PATHTASTIC. These results are now part of Biomodels database. This model results
from the extrapolation of the network of Saccharomyces cerevisiae (remote reference) thanks to the exploitation of in
silico methods including conservation of orthologous enzymes and the "mapping" of reactions according to the compartments.
The model was iteratively refined by the expertise of biologists combined to analytical predictions of “Flux Balance
Analysis”. We also proposed an applied approach based on "flows", combining a simplified model of stochastic Petri nets to
a combinatorial optimization heuristic; this study provided a use case for the Systrip tool developed in collaboration
with members of EVADoMe. Because metabolic networks can be complex and large (several thousands of biochemical reactions),
we developed a model providing a high level view of the network from which details can be accessed on demand.
Another type of biological network is at the center of a fruitful collaboration with the theme EVADoMe: regulatory
networks involving non-coding RNAs. We proposed an innovative approach to analyse these networks based on RNAV (rna
Navigator), a visual analysis software we developed for these networks modeled as graphs of interactions between RNA.
Computing distances between trees, or being able to build a “consensus” or “average” tree, is fundamental when comparing
biological structures (RNA’s, plants) encoded as trees. Algorithms on sequences and trees have been successfully applied
to musical sequences.