Jacques Nicolas

Artificial Intelligence and Bioinformatics

published or not. The documents may come

L'archive ouverte

Introduction

The links between Artificial intelligence and Bioinformatics are long-standing and strong. J. Lederberg, a professor of genetics from Stanford interested in exobiology, pointed out in the early 1960's the need for large biological equipments to be assisted by sophisticated programs [START_REF] Hundley | Multivator-a biochemical laboratory for martian experiments[END_REF]. At a time when personal computers did not exist and the amount of data was measured in Kbytes, J. Lederberg shared working relationships with E. Feigenbaum and J. McCarthy and expressed visionary ideas in this small NASA report:

In the experimental sciences ... applications will involve searching through data accumulations like spectra and other physical properties, the experimenter forming generalizing hypothesis and using the computer to test them against the file. Experienced insight into the role of the human and machine components of these systems should be invaluable in the further development of artificial intelligence, the programming of machines to simulate as far as possible those human cognitive processes that we begin to understand.These generalizations of human intellectual capability, and their delegation to Jacques Nicolas Univ. Rennes, Inria, CNRS, IRISA, Rennes, France, e-mail: jacques.nicolas@inria.fr machines, continue to refine the strategic role of the human element and to give it increasing leverage in the solution of complex problems.

At the same time, Artificial intelligence was looking at complex, real-world problems to stimulate this science and get some measurable impact of its outcomes. The DENDRAL project, an expert system recognizing organic compounds from mass spectrometry data, was one of the first outcomes of these efforts [START_REF] Lindsay | Dendral: A case study of the first expert system for scientific hypothesis formation[END_REF]. It introduced task-specific knowledge about a problem field as a source of heuristics, and paved the way for proteomics studies. One of the first success twenty years later was Protean, a system that aimed to interpret NMR data to determine protein three-dimensional structures [START_REF] Hayes-Roth | PROTEAN: Deriving protein structure from constraints[END_REF]. It also initiated the development of realistic Machine Learning applications with Meta-Dendral, which was a system that learnt the rules necessary for Dendral from (spectra, structure) pairs [START_REF] Feigenbaum | Dendral and meta-dendral: roots of knowledge systems and expert system applications[END_REF]. Note that surprisingly enough, the assistance for the interpretation of mass spectra remains in high demand in biology, whether for studying small objects like peptides, glycans or various metabolites as well as for the study of larger molecular complexes. This mutual interest has not decreased over time and it is not an exaggeration to say that the contributions or the need for Artificial Intelligence may be found everywhere in bioinformatics.

A Major Application Field for Artificial Intelligence

Artificial Intelligence takes a close interest in the development of bioinformatics for at least two reasons. The first one dates back to the very beginning of Artificial Intelligence, when living organisms were used as a source of inspiration for the design of computational methods that were more robust to the treatment of real data, including the tolerance of uncertain and imprecise data, auto-adaptation and learning skills (see also Chapter 9 of this volume). Most of these methods form the basis of what is called soft computing: neural networks (see Chapter 12 of Volume 2), evolutionary algorithms such as genetic algorithms or evolution strategies, immunological computation and various optimization techniques such as swarm or ant colony optimization (see Chapter 2 of Volume 2), and uncertainty logics such as fuzzy set or possibility theory (see Chapter 3 of Volume 1). The second one dates back to the beginning of the century, when Biology became a data-intensive field of science, with the emergence of numerous instruments scanning life at the molecular level.

In fact, Biology is not just a science of data, it is also a science of knowledge. From this point of view, there is a clear gradient from Physics to Chemistry then Biology in the complexity of structures and systems. First of all, living organisms store information in a discrete way in complex molecules and contain many symbolic machines to decipher the corresponding code (e.g. polymerases, ribosomes, and spliceosome). But life may also be characterized by the presence of many context-dependent causal influences related to biological functions [START_REF] Walker | The algorithmic origins of life[END_REF]. A cell state is determined not only by its genetic code but also by its history (cells have a memory) and its environment, which strongly impact the expression of genes: at any time in its life, only a small fraction of molecules in a cell will react. Biology is certainly the science par excellence of relations and dependencies, in the sense that it studies many different types of objects related by a number of different interactions appearing at different levels in a hierarchical structure of organization. The famous paradigm coined by R. Kowalski, "Algorithm = Logic+ Control" [START_REF] Kowalski | Algorithm= logic+ control[END_REF] could be rephrased as "Life = Logic+ Control" to emphasize the importance of these two components in all forms of life (although the control component does not simply define the computing strategy in this case but can have a feedback effect on the logic itself). It is thus a perfect application field of Artificial Intelligence for studies in knowledge representation, reasoning and machine learning. Moreover, Bioinformatics tackles numerous NP-hard problems that are interesting challenges for Artificial Intelligence.

Roughly speaking, the four main research tracks in Bioinformatics relate to statistics, algorithms on words ("stringology"), modeling (data bases, knowledge representation and system modeling) and combinatorial and optimization problems. The first one addresses issues that originate from the treatment of noisy observation data or from global effects of populations of variable elements like in population genetics. Although these questions are of interest to Artificial Intelligence, the contributions in this domain clearly derive from established methods in statistics. The second track led to many developments since sequences are the main source of data. Even expression data that measure the quantity of certain compounds are provided now in the form of sets of sequences. In this domain, the size of data -often many gigabytes -makes it essential to find linear analysis algorithms. Indexation techniques play a major role in achieving this goal. The last two tracks fully concern Artificial Intelligence techniques and still offer many interesting research challenges.

There were two possible ways to conduct a review on Artificial Intelligence and Bioinformatics: making a review, for each AI subfield, of existing or possible applications in bioinformatics, or making a review of problems in bioinformatics that are or would be interesting to AI people. The first choice would have been significantly imbalanced since Machine Learning and optimization in general occur in an overwhelming majority of papers [START_REF] Baldi | Bioinformatics: the Machine Learning Approach[END_REF][START_REF] Bhaskar | Machine learning in bioinformatics: A brief survey and recommendations for practitioners[END_REF][START_REF] Mitra | Introduction to machine learning and bioinformatics[END_REF][START_REF] Zhang | Machine learning in bioinformatics[END_REF][START_REF] Inza | Machine Learning: An Indispensable Tool in Bioinformatics[END_REF]. Machine learning generally faces hard problems in Bioinformatics cumulating small sample size, individual variability, high dimensionality and complex relations between data. For this reason and probably also because biology is a science that is used to cross-check various hints to draw robust conclusions, ensemble learning (e.g. bagging, boosting or random forests, see Chapter 11 of Volume 1) has been particularly studied in this context [START_REF] Yang | A review of ensemble methods in bioinformatics[END_REF]. It has been applied to various problems and showed interesting results each time, either for gene or protein expression data [START_REF] Liu | Ensemble gene selection for cancer classification[END_REF][START_REF] Piao | An ensemble correlationbased gene selection algorithm for cancer classification with gene expression data[END_REF][START_REF] Wu | Comparison of statistical methods for classification of ovarian cancer using mass spectrometry data[END_REF][START_REF] Gertheiss | Supervised feature selection in mass spectrometrybased proteomic profiling by blockwise boosting[END_REF], the prediction of regulatory elements [START_REF] Gordon | Improved prediction of bacterial transcription start sites[END_REF][START_REF] Wang | High-resolution human core-promoter prediction with CoreBoost_HM[END_REF][START_REF] Lihu | A review of ensemble methods for de novo motif discovery in ChIP-Seq data[END_REF] and a large range of other applications such as the analysis of interaction data [START_REF] Nagi | Complex detection from ppi data using ensemble method[END_REF], protein structure prediction [START_REF] Bouziane | Effect of simple ensemble methods on protein secondary structure prediction[END_REF] or automatic function annotation [START_REF] Schietgat | Predicting gene function using hierarchical multi-label decision tree ensembles[END_REF][START_REF] Galiez | VIRALpro: a tool to identify viral capsid and tail sequences[END_REF]Yang et al., 2016a;[START_REF] Smitha | Amyloid motif prediction using ensemble approach[END_REF].

As usual, applications are a driving force for methodological developments and interesting extensions of the ensemble approach have been proposed. In particular, the inclusion of feature selection in this framework has been identified as an important issue, since it is subject to instability [START_REF] Okun | Random forest for gene expression based cancer classification: overlooked issues[END_REF][START_REF] Awada | A review of the stability of feature selection techniques for bioinformatics data[END_REF][START_REF] Pes | Exploiting the ensemble paradigm for stable feature selection: A case study on high-dimensional genomic data[END_REF]. Many studies are available on this subject, ranging from a bootstrap strategy sampling and ranking data before feature extraction [START_REF] Yang | Gene-gene interaction filtering with ensemble of filters[END_REF][START_REF] Wald | An extensive comparison of feature ranking aggregation techniques in bioinformatics[END_REF] to the integration of several testing methods or selection methods [START_REF] Sheela | Combination of feature selection methods for the effective classification of microarray gene expression data[END_REF][START_REF] Brahim | Ensemble feature selection for high dimensional data: a new method and a comparative study[END_REF]. From the point of view of ensemble prediction techniques, Support Vector Machines ( see Chapter 11 of Volume 1) have been often used, either during feature selection [START_REF] Jong | Feature selection in proteomic pattern data with support vector machines[END_REF] or with different kernels [START_REF] Guan | Predicting gene function in a hierarchical context with an ensemble of classifiers[END_REF] or combined with bagging for instance [START_REF] Gordon | Improved prediction of bacterial transcription start sites[END_REF]. In general, Random Forests seem more adapted to high-dimension data, a frequently occurring case in Bioinformatics [START_REF] Diaz-Uriarte | GeneSrF and varSelRF: a web-based tool and R package for gene selection and classification using random forest[END_REF][START_REF] Lertampaiporn | Identification of non-coding RNAs with a new composite feature in the Hybrid Random Forest Ensemble algorithm[END_REF]Pashaei et al., 2017] and to providing explanations to the predictions, an increasing concern in recent literature. Bagging and boosting seem more adapted to black box predictors and small sample size and can be usefully supplemented by transfer learning techniques [START_REF] Mei | AdaBoost based multi-instance transfer learning for predicting proteome-wide interactions between salmonella and human proteins[END_REF].

This chapter aims to give a more precise view of the major current or emerging bioinformatics challenges that are of interest to Artificial Intelligence in order to encourage further works on this topic. The abundance of papers in the field prevents an exhaustive presentation of all the various topics addressed. We have made a selection that we hope is representative of the variety of themes, trying each time to give the basics necessary to understand a specific problem, a formalization of this problem and a few achievements and progresses in relation to this problem. People interested in further reading could consult general reviews like [START_REF] Hassanien | Computational Intelligence in Solving Bioinformatics Problems: Reviews, Perspectives, and Challenges[END_REF][START_REF] Hassanien | Computational intelligence techniques in bioinformatics[END_REF] or articles that are oriented towards a particular subfield of AI such as agents [START_REF] Keedwell | Intelligent bioinformatics: The application of artificial intelligence techniques to bioinformatics problems[END_REF][START_REF] Merelli | Agents in bioinformatics, computational and systems biology[END_REF] or knowledge discovery [START_REF] Holzinger | Knowledge discovery and interactive data mining in bioinformatics-state-of-the-art, future challenges and research directions[END_REF]. For the field of Bioinformatics itself many introductory texts exist, see for instance [START_REF] Singh | Introduction to bioinformatics[END_REF][START_REF] Ramsden | Bioinformatics: An Introduction[END_REF]. Before reviewing the research work and getting to the heart of the subject, we begin with a brief introduction to the different types of data processed in bioinformatics.

Bioinformatics: Analyzing Life Data at the Molecular Level

Living cells are made of a large variety of molecules of different types performing different functions. Apart from water, the main constituents are biopolymers, i.e., molecules forming long chains of elementary components linked by covalent bonds, which can be considered at an abstract level as texts on fixed alphabets. There are four main classes of biopolymers: DNA, RNA, proteins and glycans.

The best-known kind of macromolecule is made of DNA and holds genetic information. DNA is made of four components (bases) represented by four letters (A, T, G, and C) that match together to form in most cases a double strand (A with T and C with G being the canonical matches). The DNA text is highly structured and includes regions coding for genes and others coding for the regulation of these genes. This structure differs depending on the absence of a nucleus in cells (bacteria and archaea) or the containment of DNA in a nucleus (eukaryotes). The order of magnitude of genome lengths is 10 6 bp (letters) for bacterial genomes and 10 9 bp for eukaryotes. Basically an organism's DNA is the same in all its cells but DNA is not a long quiet river: it can be modified by so-called epigenetic factors like DNA methylation or histone modifications. It is also well known that DNA can acquire mutations that cause genetic differences (polymorphism) between individuals. The most common are single nucleotide point mutations called SNPs (one SNP every 1000 bases for human individuals). However, mutations can occur throughout life on any cell's DNA and are then transmitted to the daughter cell lineage. All these transformations can potentially favor the appearance of diseases like cancer. An ancient but still topical challenge is the classification of species and the reconstruction from their DNA of their evolution scheme from ancestral species (see section 6). A main challenge on DNA is the annotation problem, which consists in discovering the functional content encoded by the nucleotide sequences: where are the genes and other genomic units and can we relate them to known elements ? For simple organisms it is routinely achieved by laboratories, using off-the-shelf software pipelines, but it remain a complex task for higher eukaryotic organisms (see section 3). A more recent challenge is the representation and management of all variations that occur between individuals or even individual cells, a challenge that is also central to RNA.

The second macromolecule, RNA, also made of four nucleotides (A, U, G and C), has been particularly studied in the last fifteen years and shown a key role in the regulation processes. RNA is thought to have been a precursor molecule to life on earth [START_REF] Robertson | The origins of the rna world[END_REF]. RNA is a biochemical mediator having both the capacity to store information as DNA and to act as a biochemical catalyst like proteins. The primitive quasi-life forms of viruses are made of RNA. It is in most cases a single-strand folded onto itself, giving rise to various structures in space related to their function. A number of RNA types exist (a typical eukaryotic cell can contain ten of thousands of RNA species) that are built from DNA through a process called transcription. In a given cell type, a specific part of the DNA is expressed in RNA, generally with multiple copies. One of the most important RNA species is messenger RNA (mRNA), expressed and matured from regions of the DNA called (protein) genes and acting as an intermediate for the synthesis of proteins (through a process called translation). It is estimated that in the human genome 85% of DNA is transcribed in RNA and 3% of DNA encodes protein-coding genes. To give an order of magnitude of cell complexity, approximately 350,000 mRNA molecules are present in a single mammalian cell, made up of approximately 12,000 variants with a typical length of 2 kb. The abundance of each variant can range from 10,000 to a few copies. Some mRNAs comprise 3Other types of RNA are used for gene expression regulation, translation or RNA processing. The RNA level of expression of thousands of genes in a sample of cells can be measured simultaneously (a process called gene expression profiling) for different conditions and at different time points. A major challenge of RNA analysis is the determination of differentially expressed genes across experimental conditions, development stages, or healthy/pathological conditions [START_REF] Han | Advanced applications of rna sequencing and challenges[END_REF]. Beyond expression of individual genes, advanced studied are looking for gene sets [START_REF] Huang | Systematic and integrative analysis of large gene lists using david bioinformatics resources[END_REF] (see section 2) or even gene networks, either to represent co-expression networks or differentially expressed biological pathways [START_REF] Khatri | Ten years of pathway analysis: Current approaches and outstanding challenges[END_REF] (see section 5). Another challenge on RNA is the search of expressed gene variants that are variations from the same DNA coding region that produce alternative transcripts (alternative splicing) depending on the environment (see section 3).

The falling cost of sequencing technology for these two types of nucleic acid chains is having a marked impact on the biological research community. Essentially, sequencing projects have generally become small-scale affairs that are now carried out by individual laboratories.

Proteins, the third type of macromolecule are the main actors of the cell, performing a large range of functions ranging from cell structure (e.g. collagen) to metabolic reaction catalysis (enzymes), transport, cell signaling, and DNA replication. Proteins control the continuous component of life dynamics: essentially all biochemical reactions have continuous rates depending on protein expression. The building blocks of proteins are amino acids (AA, 20 amino acids in the genetic code) that are bonded together by peptide bonds. When two amino acids combine to form a peptide, water is removed and what remains of each amino acid is called a (amino-acid) residue. The order of magnitude of protein lengths is 10 3 AA. Proteins fold into 3D-structures called tertiary structures that depend on their amino acid sequence and determine their function. A protein tertiary structure is slightly flexible and may adopt several conformations but it may be described at a more abstract level in terms of simpler secondary structure elements (mainly alpha helices and beta sheets, the rest being generally classified as random coils) or, on the contrary, be assembled into dimeric structures or large protein complexes that function as a single entity. We know that the structure of proteins is crucial to understanding their role. Unlike nucleic polymers, even the sequence of proteins is hard to obtain since proteins are often transformed by post-translation modifications (e.g. the most common modification, glycosylation is estimated to occur in greater than 70% of the eukaryotic proteins, see the next paragraph on polysaccharides). Protein structures can only be obtained through timely and costly experiments and a long-standing challenge in bioinformatics is to predict this structure from the sequence (see section 4). Another particularly active field of research because of its importance for human health is the development of new drugs (see section 7).

A more recent topic from the point of view of bioinformatics relates to nonribosomal peptides (NRP), which are small chains of amino-acids (size less than 50 AA) that are essentially produced by microorganisms, using specialized large (complexes of) peptide-synthetase enzymes instead of ribosomes. Their characteristic is to use a large alphabet (more than 300 variations of amino-acids have been identified, compared to the 20 AA in aminoacids) and have a linear, branching and/or cyclical structure. These natural peptides have many biological functions (antibiotics, immunosuppressants, antifungals, toxins) that are of high interest for medicine and biotechnology. In fact, there is also a largely unexplored space of ribosomal peptides that share many of the structural and enzymatic features of NRPs, paving the way for a discipline in its own right called peptidomics [START_REF] Dallas | Current peptidomics: Applications, purification, identification, quantification, and functional analysis[END_REF].

The last type of biopolymer are polysaccharides, which are carbohydrate structures made of long chains of monosaccharide elements often called single sugars (mainly 4 types but many hundreds structural isomers and variants have been identified), typically joined with covalent glycosidic bonds. Polysaccharides are often a reserve of energy for organisms (e.g. starch may be converted into glucose) or can have a structural role (e.g. chitin used in composite materials forming the exoskeleton of insects or the shells of crustaceans and mollusks, or cellulose used as a dietary fiber). They are crucial to the functioning of multi-cellular organisms and are implied in protein folding, cell-cell interaction, immune response (antigenantibody interaction) and epithelium protection, serving as mediators (or carriers) of many information transmission processes. Their structure can be linear or branched. Polysaccharides are particularly important in biology when associated with other elements and are referred to as glycans in this context. At an abstract level, glycans can be modeled by ordered labeled trees. The main glycans are found associated with proteins (glycoproteins or proteoglycans) and lipids (glycolipids). The modification of some protein amino acids after their translation by glycans is called glycosylation. The identification of glycan structures (sequencing) remains a complex experimental process, as is the identification of glycosylated sites in a protein. Unlike other biopolymers, progress in glycobiology is recent [START_REF] Frank | Bioinformatics and molecular modeling in glycobiology[END_REF]. Due to the importance of glycans in practical applications (drug targets, biofuels, alternatives to petroleum-based polymers), there is, however, no doubt that this field will experience major developments in the coming years.

When the entire set (or a large set) of elements of a certain type is available through high-throughput experiments, they are called omics data. For the four types described, the corresponding terms are genome, transcriptome, proteome and glycome. One could add another high-throughput source of information, the bibliome [START_REF] Grivell | Mining the bibliome: searching for a needle in a haystack?[END_REF][START_REF] Sarkar | Mining the bibliome[END_REF], since millions of documents are published in Biology and can be considered as raw data out of reach of manual treatment (see next section).

Many biopolymers work by interacting with other biopolymers. For instance the regulation of gene expression is ensured by many mechanisms involving RNA (e.g., microRNA are small non-coding RNA molecules that interact with mRNA to regulate gene expression after transcription) or proteins (e.g. histones are proteins interacting with DNA in a structure called chromatine that organizes the very long DNA chain of a chromosome into structural units). Proteins can act on DNA by attaching to a specific sequence of DNA adjacent to a gene that they regulate (transcription factor) or by generating complementary DNA (cDNA) from an RNA template (reverse transcriptase, a mechanism used by retroviruses). Protein kinases modify other proteins and are essential for the transmission of external signals within cells. All these interactions between numerous compounds occur within networks at different levels (in a compartment inside the cell, in the cell or in the extracellular matrix surrounding the cells,in a tissue or in a microbiota) and at different time scales and a great deal of research addresses this subject (see section 2 and 5).

Data and Knowledge Management

In molecular biology, the flow of data from multiple high-throughput observation devices combined with the results of (semi-)automated analyses of these observations is collected in many databases (the journal Nucleic Acids Research, which publishes each year a catalogue of such databases in a special issue, lists for instance 152 databases in 2017, 54 of which are new. [START_REF] Galperin | The 24th annual nucleic acids research database issue: a look back and upcoming changes[END_REF]). The difficulties of analyzing observations to obtain functional knowledge about the organisms studied are not discussed here. The complex process of functional annotation of data is indeed more a matter of software engineering than artificial intelligence. An exception is the use of multiple agents to ease this task [START_REF] Jiang | Assigning biological functions to rice genes by genome annotation, expression analysis and mutagenesis[END_REF]. Predictions made by machine learning methods are treated in other sections and the next section for instance deals with the annotation of genes.

This section is about data and knowledge management. The maintenance of all these databases quickly became a nightmare due to the rapid increase in data with different levels of quality, which requires frequent releases, changes in database schema and an updating process that grows generally quadratically with the number of organisms. Moreover, the question of integration of all these sources of data is a central concern for biology. It is managed through the creation of ontologies, the representation of graphs linking heterogeneous data and, to a small extent, through automated reasoning [START_REF] Blake | Beyond the data deluge: Data integration and bio-ontologies[END_REF]. The stake here is to support and leverage the transition from a world of isolated islands of expertise knowledge to a world of inter-related domains.

In terms of data integration, the requirements are:

• Identify entities (unambiguously); • Describe them (i.e., their properties and their relations with other entities) and ensure each element of a description is itself identifiable;

• Combine descriptions from multiple places (typically different aspects of the same entity); • Support semantically reach querying and reasoning on descriptions.

Over the last decade, Semantic Web technologies such as RDF, SPARQL and OWL from the W3C have provided the infrastructure supporting the linked Open Data initiative [START_REF] Bizer | Linked data-the story so far[END_REF] (see Chapter 6 of this volume). This has played a key role for integrating bioinformatics data [START_REF] Cannata | A semantic Web for bioinformatics: goals, tools, systems, applications[END_REF][START_REF] Post | A semantic web approach applied to integrative bioinformatics experimentation: a biological use case with genomics data[END_REF][START_REF] Bellazzi | Big data and biomedical informatics: a challenging opportunity[END_REF].

Information Extraction in Biological Literature

Despite strong and growing efforts to normalize data formats and collect observations in databases, a large amount of information relevant to biology research is still recorded as free text in journal articles and in comment fields of databases [START_REF] Hirschman | Accomplishments and challenges in literature data mining for biology[END_REF]. Since interactions are ubiquitous in biology, retrieving interactions between identified components is a very important task. This assumes that different naming variants of a same component have first been recognized and it is far from easy due to early lax practices: use of common names (e.g. bag, can, cat, or, six, top are all gene or protein names), use of synonyms (e.g. can as well as n214 are aliases for nucleoporin 214), ambiguous names (e.g. the string cat may refer to enzyme Chloramphenicol acetyltransferase in bacteria, or a gene for the catalase enzyme in Human), or terms used in other biological contexts (e.g., shotgun, which can refer both to DE-cadherin gene or to a technique used for sequencing long DNA strands) [START_REF] Chen | Gene name ambiguity of eukaryotic nomenclatures[END_REF].

An interesting recent development concerns the rapprochement between two communities, namely expert curators who read each publication to extract the relevant information in a standardized computationally tractable format and specialists in text-mining applied to biologically relevant problems. Manual curation is a very complex task that will likely need human experts over the long term, but it does not scale with the growth of biomedical literature (estimated in 2016 at more than 3 publications per minute for the main database of citations for biomedical literature Pubmed, which comprises more than 27 million citations). In 2007, the team working on RegulonDB, a carefully curated database on transcriptional regulation in E. coli, showed that 45% of the knowledge content could be extracted using rule-based natural language processing and that it allows for an additional 0.15% new rules to be proposed, of which a quarter was subsequently shown to be accurate [START_REF] Rodríguez-Penagos | Automatic reconstruction of a bacterial regulatory network using natural language processing[END_REF]. The BioGRID database, which systematically curates the biomedical literature for genetic and protein interaction data has been involved in a coordinated effort with the BioCreative (Critical Assessment of Information Extraction in Biology) initiative to produce the BioC-BioGRID corpus, which contains a test collection of 120 full text articles with both biological entity annotations (gene and species) and molecular interaction annotations (protein and genetic interactions) [START_REF] Islamaj Dogan | The biocbiogrid corpus: full text articles annotated for curation of protein-protein and genetic interactions[END_REF]. This collaborative work allowed for guidelines for building text-mining systems that assist curation of biological databases to be proposed and fosters further research in this area. We extracted from the previous paper a list of four tasks in full text analysis that are particularly relevant in this context:

The curator assistance problem Given the full text of a research paper in biology, solve the following tasks:

• Recognition of evidence described in the current article vs information taken from other articles; • Recognition of evidence which is supported by experimental data vs hypothetical or vague statements; • Distinction between statements describing the layout vs statements describing the results of an experiment; • Recognition of negative statements.

The OntoGene system is a state-of-the-art text mining system for the detection of entities and relationships from various items such as genes, proteins, chemicals but also drugs and diseases, implemented as web services for more flexibility. It provides standard text pre-processing tasks including identification of sections, sentence splitting, tokenization lemmatization and stemming, and can optionally perform syntactic analysis using a dependency parser (see Chapter 4 of this volume for more information on natural language analysis). It includes a module for entity recognition, using a rule-based approach, and disambiguation, using HMM-based learning from noisy data. This last point is crucial since it is hard to obtain a specialized dictionary in every domain. OntoGene has been applied to RegulonDB, a manually curated resource about the regulation of gene expression in E.coli [START_REF] Rinaldi | Strategies towards digital and semi-automated curation in Reg-ulonDB[END_REF].

Going beyond the state of the art will imply also taking into account the variety of forms in which knowledge is available in papers. As was mentioned in [START_REF] Rodríguez-Penagos | Automatic reconstruction of a bacterial regulatory network using natural language processing[END_REF], texts are not always sufficient and tables and figures and their captions contain what human curators need to generate relevant information. The recognition of evidence in particular can be greatly enhanced with such data. In this respect, the development of efficient and robust figure extraction methods [START_REF] Clark | Pdffigures 2.0: Mining figures from research papers[END_REF], able to scale to large databases of documents such as semantic scholar is certainly good news when it comes to fostering these studies.

Biological Ontologies

As Stevens et al. noted [Stevens et al., 2000],

Much of biology works by applying prior knowledge [...] to an unknown entity, rather than the application of a set of axioms that will elicit knowledge. In addition, the complex biological data stored in bioinformatics databases often require the addition of knowledge to specify and constrain the values held in that database.

The knowledge we are focusing on is mostly symbolic. It should typically support comparison, generalization, association and deduction [START_REF] Bechhofer | Why linked data is not enough for scientists[END_REF].

Such knowledge is typically represented in ontologies which Bard defines as [ [START_REF] Bard | Ontologies in biology: design, applications and future challenges[END_REF]] "formal representations of areas of knowledge in which the essential terms are combined with structuring rules that describe the relationship between the terms". In the early 1960s, the National Library of Medicine proposed a controlled vocabulary, Medical Subject Headings (MeSH), for the purpose of indexing journal articles and books in the life sciences and facilitate searching. It consists of hierarchically organized sets of terms that permits searching at various levels of specificity. the MEDLINE/PubMed article database and the NLM's catalog of book holdings. Available since a few years in RDF format, it currently contains over 28,000 descriptors accessible via 90,000 entry terms. Since then, a large number of ontologies have been developed in biology. A repository like Bioportal [START_REF] Whetzel | Bioportal: enhanced functionality via new web services from the national center for biomedical ontology to access and use ontologies in software applications[END_REF] was referencing 685 ontologies and 95M direct annotations in 2017. Moreover, a huge amount of data annotated by ontologies are now available via public SPARQL endpoints like the EBI RDF platform [START_REF] Jupp | The ebi rdf platform: linked open data for the life sciences[END_REF], which is built on the OpenLink triple store technology and allows a programmatic access to these data.

The Gene Ontology (GO) is probably the best example of a significant development in biological ontologies [START_REF] Ashburner | Gene Ontology: tool for the unification of biology[END_REF], the number of papers citing this article (more than 20000) being a good indication of its importance. GO is both a standard terminology for describing the function of genes and gene products and a corpus of evidence-based GO annotations for gene products. In 2016, it contained more than 40,000 terms and 90,000 relations, over 600,000 annotations with an experimental evidence extracted from 140,000 papers and is also regularly revised by a dedicated team and requests by the scientific community. GO consists of three independent ontologies in the form of directed acyclic graphs (DAG): "molecular function" describing activities (e.g. catalytic or binding activities) at the molecular level, "biological process" giving programs accomplished by these activities, and "cellular component" where the function occurs. Each concept includes a term (recommended name), an identifier, definition (explanation and references) and synonyms. The DAG is essentially a tree with a few children having several parents. The relationship of child to parent can be either "is_a", "part_of", "regulates" or "occurs_in".

It is associated with GO tools such as browsing, SQL querying, and the Term Enrichment Service to find terms that are significantly more present in a set of product genes than by chance. It is also supported by external tools such as Blast2GO [START_REF] Götz | Highthroughput functional annotation and data mining with the blast2go suite[END_REF], dedicated to high-throughput functional annotation of genomic sequences. For the annotation of a new sequence, Blast2GO looks for homologous sequences in sequence databases with the comparison tool Blast, transfers the anno-tation of these homologous sequences and applies various rules to enhance the final annotations given relationships between the three subontologies and other databases on protein domains and pathways and using natural language text mining to simplify or structure the annotations. Since the management of ontologies has a strong technological component and uses a lot of engineering work, there are of course generic tools that are applied to GO as for instance ontologyX [START_REF] Greene | ontologyx: a suite of r packages for working with ontological data[END_REF], a package for integrating ontologies in the R environment. As a data provider of growing importance, GO is not used solely for annotation purpose but as a source of features for prediction purpose. For instance, the issue of predicting the subcellular location of a protein has been addressed by machine learning methods including GO terms as discriminant features of protein locations [START_REF] Mei | Multi-label Multi-Kernel Transfer Learning for Human Protein Subcellular Localization[END_REF][START_REF] Li | An ensemble classifier for eukaryotic protein subcellular location prediction using gene ontology categories and amino acid hydrophobicity[END_REF][START_REF] Wan | HybridGO-Loc: Mining hybrid features on gene ontology for predicting subcellular localization of multi-location proteins[END_REF]. The idea in [START_REF] Mei | Multi-label Multi-Kernel Transfer Learning for Human Protein Subcellular Localization[END_REF] is to retrieve proteins homologous to the target sequence by looking for matches against the InterPro protein signature databases (InterproScan), to extract their GO terms in the three subontologies, then to learn a kernel for a SVM to transfer the appropriate GO terms on the target protein and use them for predicting the location. The interest of using GO or other ontologies through transfer learning to enhance predictions has been confirmed in other studies such as the prediction of the associations between human genes and phenotypes based on human protein-protein interaction network [START_REF] Petegrosso | Transfer learning across ontologies for phenome-genome association prediction[END_REF].

In recent years, the tendency has in fact been to transform the ontology into a true knowledge base by integrating other sources (for instance the database of molecular interactions IntAct), by adding axioms and biological reasoning abilities, and by working on more elaborated representations as for instance for the description of biochemical pathways [The GO Consortium, 2017]. There is thus a strong opportunity for the IA community to transfer and test some tools in this domain (see Chapter 6 of Volume 1). The Web Ontology Language (OWL) is used in advanced versions of GO that include "has_part" and "occurs_in" relations and propose a fully axiomatized content giving access to cross ontology relationships. These other Open Biological Ontologies come from OBO, a consortium with an editorial committee that ensures coordinated development in biological and medical sciences of ontologies. They are designed to be interoperable and logically well-formed and to incorporate accurate representations of biological reality [START_REF] Smith | The obo foundry: coordinated evolution of ontologies to support biomedical data integration[END_REF]. Thus, GO includes, for instance, links to (small) Chemical Entities of Biological Interest (Chebi [START_REF] Hastings | The chebi reference database and ontology for biologically relevant chemistry: enhancements for 2013[END_REF]) and a multi-species anatomy ontology (Uberon, [START_REF] Mungall | Uberon, an integrative multi-species anatomy ontology[END_REF]). From the point of view of the integration of different ontologies, a central problem is that of alignment, where one tries to match the entities with each other [START_REF] Shvaiko | Ontology matching: state of the art and future challenges[END_REF]. From the point of view of knowledge representation, a form of negation has been introduced in GO: when a gene product is expected to have a certain activity but it is known from experiments that it is not the case, it is emphasized with a Not qualifier [The GO Consortium, 2017]. Although there are currently very few negative annotations in GO, this is a clear advance with respect to reasoning. The full exploitation of biological knowledge expressed in OWL needs highly efficient reasoners on the underlying descriptive logics. A good example of such a framework is Aber-OWL [START_REF] Hoehndorf | Aber-owl: a framework for ontology-based data access in biology[END_REF], which uses the ELK reasoner. The main fulltext index of the scientific literature in Biology, PubMed, is built on top of Aber-OWL, and give an ontology-based access to more than 27M citations for biomedical literature from MEDLINE, life science journals, and online books.

The field of biological ontologies provides a large scale experimental field for researches at the crossroads of Semantic Web and Knowledge Bases. It is led by a dynamic community that proposes many research issues and we will just point at two of them to conclude this section. Tracking the inconsistencies in such complex knowledge bases subject to many types of updates (new terms, obsoletion, new name for a term, term merge, etc.) is a research task of high importance. In [START_REF] Chen | Detecting inconsistency in biological molecular databases using ontologies[END_REF] authors propose an ontology-based framework to detect the inconsistency in biological databases. This task is approached as a quality control problem in [START_REF] Ghisalberti | Quality controls in integrative approaches to detect errors and inconsistencies in biological databases[END_REF]. In [START_REF] Park | Gochaseii: correcting semantic inconsistencies from gene ontology-based annotations for gene products[END_REF], as many as 27 databases are used to check GO and, besides syntactic errors, semantic inconsistencies are checked concerning redundancy and use of species-specific definitions. A more global Belief Revision approach is proposed in [START_REF] Deagustini | Datalog+-ontology consolidation[END_REF], where consolidations operators are built satisfying a fixed set of properties, based on kernel contraction and restoration and performed by the application of incision functions that select formulas to delete (conflicts). Although developed forDatalog ± ontologies, these operators can be applied to Description Logics and it seems to be an interesting research direction for bio-ontologies.

As coined in [START_REF] Matentzoglu | Inference inspector: Improving the verification of ontology authoring actions[END_REF], building ontologies using OWL is a difficult a, error-prone process and these errors have to be made explicit to authors. A general technique that seems to give good results in limited experiments is to improve the understanding of correct and efficient authoring actions by providing entailment set changes. In his perspectives, the GO consortium has also announced moving towards the introduction of relations between annotations for the function description of gene products in the context of a larger biological process. The new model, called LEGO for "Logical Extension of the Gene Ontology" is a neat progress towards the study of causality in biological networks. The LEGO formalism will define how different traditional GO annotations can be combined into a larger 'model' of gene and system function. Preliminary studies have been presented in [START_REF] Huntley | A method for increasing expressivity of gene ontology annotations using a compositional approach[END_REF]. The idea is to associate to standard annotations (a pair single gene product GP-single GO term) a relational extension of the form Relation(Entity) depending on the gene product, where Relation concern either a chemical (molecular relation) or any other entity like a cell type (contextual relation). This extension is interpreted internally as a relation Relation(GP, Entity).

Gene and Non-Coding RNA Prediction

Gene prediction is a task that occurs at the beginning of a new genome annotation, just after completing DNA sequencing. It refers to the process of identifying the regions of genomic DNA that encode protein-coding genes or RNA genes. The prediction of protein genes of prokaryotic genomes (bacteria and archaea) is relatively easy since they usually appear without interruption in the sequence, as a single block named open reading frame (ORF). A remaining difficulty is the prediction of ribosomal frameshift events, a particular mechanism present in all organisms including viruses, which causes a shift by one or two nucleotides when translating the mRNA code, thereby changing the ORF and the protein code. It is generally treated through HMM prediction [START_REF] Kislyuk | Frameshift detection in prokaryotic genomic sequences[END_REF][START_REF] Antonov | Genetack: frameshift identification in protein-coding sequences by the viterbi algorithm[END_REF], but the difficulty to obtain experimentally validated frameshifts has reduced opportunities for model learning. The recently developed ribosome profiling technique (Ribo-Seq) that allows precise mapping of the locations of translating ribosomes on mRNAs should boost interest in research on this topic [START_REF] Michel | Observation of dually decoded regions of the human genome using ribosome profiling data[END_REF].

For protein of eukaryotic genomes, genes are made of a mosaic of blocks and an important subtask is the search of possible isoforms called splicing variations made of the combination of specific coding parts called exons, which are built by a special editing process during or just after transcription (transformation of the DNA code in a RNA molecule). Alternative splicing occurs for instance in half of the human genes, largely increasing the diversity of proteins and their specificity in different tissues. A gene is in this case the set of all the exons appearing in these isoforms. Splicing uses faint signals that are not completely understood and the prediction of alternative splicing variants remains a primary challenge in gene prediction. Moreover, part of the remaining sequence (called introns) can be used in some rare variants. In fact, the definition of a gene has evolved significantly with discoveries and it is likely that much remains to be discovered in this area and requires new developments in bioinformatics. Examples of recent advances in gene knowledge include chimeric mRNAs that are produced by joining exons from two or more different gene loci [START_REF] Lai | Fusion transcript loci share many genomic features with non-fusion loci[END_REF].

Historically, the development of gene prediction algorithms was based solely on the DNA sequence since the technology was still limited with respect to RNA sequencing. In order to have access to transcribed sequences, people were generating Expressed Sequence Tag (EST), short sequences of DNA synthesized from mRNA by special enzymes making the reverse transformation. EST are still in use for genetic studies of populations (simple sequence repeat (SSR) markers are ideal for this purpose). Since then, the RNA-Seq technology has given far more efficient access to transcribed sequences, introducing a small revolution for gene discovery, and other hints, such as mass spectrometry data, are also available to help finding proteincoding genes. Another evolution is due to the accumulation of genome sequences that enables the transfer of knowledge about these genomes to building new ones. We briefly review these aspects, starting with the analysis of DNA sequences. A review of practical tools is available in [Hoff and Stanke, 2015].

Main gene finders, such as GeneMark, GeneID, GlimmerHMM, AUGUSTUS, and SNAP, have been developed to recognize specific features in the DNA sequences (translation start site, sequence composition, splice site patterns, etc.) whose cumulated presence is signaling the presence of genes. They also frequently include the prediction of functional elements closely associated to genes, such as regulatory regions. In most cases HMMs form the basis for modeling these patterns, with tools having pre-built HMM models for several model species and that can tune the parameters of these probabilistic state models to a new genome by training them on a user-provided subset of known genes. The recent tendency is to include more complete learning capacities in integrated frameworks: see for instance WebAugustus [Hoff and Stanke, 2015] and SnowyOWL [START_REF] Reid | Snowyowl: accurate prediction of fungal genes by using rna-seq and homology information to select among ab initio models[END_REF] for Augustus and the work of Lomsadze et al. for Genmark [START_REF] Lomsadze | Gene identification in novel eukaryotic genomes by self-training algorithm[END_REF][START_REF] Lomsadze | Integration of mapped rnaseq reads into automatic training of eukaryotic gene finding algorithm[END_REF](Genmark-ET and ES).

The technology used to acquire RNA sequences has made major improvements over recent years, firstly through high-throughput sequencing of short reads (e.g. sequences of length 150), then much longer sequences (e.g. of length 1500). Despite these improvements, the state-of-the-art of transcript-based approaches for gene recognition is still unsatisfying, and there is surely room for advanced AI techniques in the analysis of these new data. This is mainly a combinatorial issue of assembling full transcripts from the fragments due to the diversity of situations (a giant jigsaw puzzle), the difficulty in quantifying the expression levels (solving a system of linear Diophantine equations) and the difficulty in recognizing and discarding long untranslated regions that may contain fragments close to protein-like coding sequences. The integration of RNA-seq data in the training of gene finders has been proposed in [START_REF] Lomsadze | Integration of mapped rnaseq reads into automatic training of eukaryotic gene finding algorithm[END_REF]Hoff et al., 2015]. In [START_REF] Pertea | Stringtie enables improved reconstruction of a transcriptome from rna-seq reads[END_REF], transcript reconstruction and quantification are solved simultaneously, the quantification question being stated as a maximal flow issue on an alternative splice graph of overlapping fragments that authors solve with a specific breadth first search algorithm.

In the domain of health, individual variations (mutations) that occur in genes are known to be a major factor of diseases directly or indirectly, and the increasing access to individual whole-genome sequences could be the vector of a deep change in care strategy generally referred to as "precision medicine" [START_REF] Aronson | Building the foundation for genomics in precision medicine[END_REF]. As mentioned in the introduction to this section, splicing is an essential feature of eukaryotes. It is estimated that at least 90% of human genes have splicing variants. Some mutations directly impact exons and their translation into viable proteins, but missplicing due to mutations in introns is also an important source of human diseases. It is possible in some cases to align the RNA sequences on a reference genome and this strategy is often chosen in the case of the human genome and does not use artificial intelligence. The state-of-the-art in this domain has reached a high level of sensitivity [START_REF] Medina | Highly sensitive and ultrafast read mapping for rna-seq analysis[END_REF], using the combination of an indexing method (Burrows-Wheeler Transform) in order to obtain a first set of high-quality mapped reads and a constrained dynamic programming search (Smith-Waterman) for resolving more difficult splicing variants. However, the problem remains difficult in the absence of a reference genome or with highly altered variants (tumour tissue sampling).

The prediction of splice sites (frontiers between introns and exons) include donor (exon/intron boundary) and acceptor (intron/exon boundary) splice site recognition and the recognition of a particular structure called branchpoint element. It generally occurs on a window of 100-150 nucleotides sliding on the sequence. Many machine learning methods have been used for the donor and acceptor prediction tasks, including Neural Networks, Decision Trees, HMM, and Support Vector Machines, or a combination of them. For instance, [START_REF] Wei | A novel splice site prediction method using support vector machine[END_REF] trains a first order Markov model to generate sequence features on the conditional probability of presence of each aminoacid within the site and outside the site. These and other features (e.g. trinucleotide compositions) are first subject to a feature selection step, then used to build a SVM model from a training set. It has been slightly refined by Pashaei et al. in a series of papers showing the difficulty to choose methods that have simultaneously a high accuracy, use a few parameters and are efficient [Pashaei et al., 2016a[Pashaei et al., ,b, 2017;;Pashaei and Aydin, 2017].They first introduced a boosting algorithm (Ad-aBoostM1 with C4.5 for the weak learner), then introduced second order Markov models, then replaced the SVM and boosting method by a bagging algorithm (Random Forest classifier) and came back to Adaboost with another feature encoding scheme.

At a higher level, alternative splicing leads to multiple transcripts from a single gene, using different pairs of donor/acceptor splice sites. These splicing variants can be recovered by using EST data or RNA sequences [START_REF] Pirola | Pintron: a fast method for detecting the gene structure due to alternative splicing via maximal pairings of a pattern and a text[END_REF]. The basis for the representation of all variants is a splicing graph, i.e. a DAG whose vertices are blocks (maximal sequences of exons fragments that always appear together in all variants) and edges correspond to adjacency in at least one variant [START_REF] Lacroix | Exact transcriptome reconstruction from short sequence reads[END_REF]. From a set of sequencing reads, it is possible to obtain a weighted graph, i.e.the number of reads(abundance) supporting each edge. Then the transcriptome reconstruction problem consists to find for each possible path (and thus each variant) in the splice graph an abundance compatible with these data and the possible errors in sequencing. It is an integer linear programming issue that has not always a solution but that seems to be solvable in practice if the list of all variants is given [START_REF] Lacroix | Exact transcriptome reconstruction from short sequence reads[END_REF]. A variant of this graph has been proposed in [START_REF] Beretta | Modeling alternative splicing variants from rna-seq data with isoform graphs[END_REF] where it is the vertices rather than the edges that are weighted, each weight being the size of the sequence associated to a block. Authors are looking for a minimal-weight splicing graph having the same set of k-mers (string of length k) than the set of reads.

Protein Structure Prediction and Computational Protein Design

The issue of predicting the structure of a protein from the mere observation of its sequence is one of the oldest challenges in bioinformatics and still warrants much study. Given a protein sequence and some fixed environmental conditions, the folding in space of this sequence is a deterministic process that leads to a specific conformation, up to small vibrations. The best source of protein structures, PDB (Protein Data Bank), contained 42,000 distinct proteins with known 3D structures in 2017. In contrast, the main source of protein sequences, UniProtKB, contained more than 500,000 reviewed entries and almost 100 M automatically annotated sequences. This gives an idea of the gap between experimental capacities and the needed knowledge of structure annotations.

The structure prediction research community is very dynamic both because it is a fundamental research issue relating to understanding the basic building blocks of life from a structural and functional point of view and also because it has, since 1994, been centered around a very challenging competition, a kind of "Olympic Games" known as CASP (Critical Assessment of protein Structure Prediction, http://predictioncenter.org). Targets for structure prediction are either structures about to be solved by X-ray crystallography or NMR spectroscopy and that will be available in the Protein Data Bank at the end of the competition. A hundred teams are participating in about ten prediction categories and results are published in the journal Proteins [START_REF] Moult | Critical assessment of methods of protein structure prediction (CASP)-round xii[END_REF].

Since the prediction of 3D structures is a very complex issue, a number of subproblems have been defined. At the lowest level, one can look for secondary structures, where each position in the sequence is assigned a conformational state between a small number of possibilities (generally 3 classes, alpha helix, beta strand or coil). Other predictions can relate to physical measures such as solvent accessibility or localization information such as transmembrane regions or protein subcellular localization. It can also relate to particular bonds like disulfide bonds or hydrophobic interactions. Finally, a very useful intermediary level of representation for protein structures is made by contact maps, which points to close positions within the structure (distance less than a given threshold).

Secondary Structure Prediction, a Benchmark Model for Structural Bioinformatics

Secondary structure prediction (SSP) is the first step to understanding the 3D structure of a protein and is essential in the kinetics of protein folding. It is certainly one of the bioinformatics issues on which the highest number of machine learning methods has been tested, due to an early effort to standardize secondary structure states and accuracy measures and propose benchmark data sets. In [START_REF] Yang | Sixty-five years of the long march in protein secondary structure prediction: the final stretch[END_REF], 266 methods were counted between 1973 and 2016, a research effort that underscores the importance of bioinformatics problems for machine learning development. Currently, most methods are used to predict several structural parameters and, particularly, solvent accessibility. Secondary structures are local regular conformations spontaneously formed as an intermediate during protein folding. They are defined by specific hydrogen bonding arrangements between the amino and carboxyl groups in the backbone of the molecule. The prediction is generally made on 3 classes (alpha helices, beta sheets and random coils, see section 1) and achieved on a window of about 15 aminoacids sliding on the protein sequence. The current tendency is to work on 8 classes. The interest of ensemble learning has been pointed out very early on this problem [START_REF] Guermeur | Improved performance in protein secondary structure prediction by inhomogeneous score combination[END_REF], for instance by using Multivariate Linear Regression to combine the scores of multiple classifiers.

Generally, a two-step procedure is used: one for a raw prediction of the class, and one for smoothing this prediction over the sequence, taking into account correlations between several positions. Decisive progress then came from the introduction of more domain knowledge into the prediction process. First, instead of only considering the protein sequences, the fact that all proteins are related through evolution has been taken into account by looking for known proteins similar to the one studied [START_REF] Rost | Prediction of protein secondary structure at better than 70% accuracy[END_REF]. It not only served to improve the prediction score but also to define a position-specific reliability index pointing at regions of the proteins with high confidence predictions. Once similar proteins have been collected, a multiple alignment of their sequences provides information about the importance of each position that can be used in the classification procedure, for instance in the form of a profile HMM [START_REF] Eddy | Profile hidden markov models[END_REF][START_REF] Cuff | Application of multiple sequence alignment profiles to improve protein secondary structure prediction[END_REF]. Together with an ensemble strategy, it has given birth to three important prediction servers based on neural networks, PSIPRED [START_REF] Mcguffin | The psipred protein structure prediction server[END_REF], Distill [START_REF] Baú | Distill: a suite of web servers for the prediction of one-, two-and threedimensional structural features of proteins[END_REF], and JPred [START_REF] Drozdetskiy | Jpred4: a protein secondary structure prediction server[END_REF].

The current state of the art introduces another source of knowledge, the PDB, which has sufficiently grown to propose a large set of non-redundant protein chains (5800) with a known 3D structure and thus a known secondary structure. A simple strategy has thus been proposed in [START_REF] Magnan | SSpro/ACCpro 5: almost perfect prediction of protein secondary structure and relative solvent accessibility using profiles, machine learning and structural similarity[END_REF], where the basic prediction uses a bidirectional recursive neural network and the sequence regions with sufficient similarity with some of these chains are assigned with their majority secondary structure.

As stated in this paper, the problem seems virtually solved with such a strategy, but it is not the end of the story. Using existing structures as templates does not convey any information on the logics of folding, although it must exist since the number of possible structures seems very small as compared to the variety of sequences and the size of the conformation space. Any progress in prediction methods for SSP may benefit other more difficult prediction problems on protein structure, but this requires going beyond case-based reasoning to discover the folding logic.

If no, it seems likely that the complete 3D prediction problem will remain hard to solve. This is why people continue to measure accurately the contribution of prediction methods without the input of structural information and even without the use of homology with other sequences.

The contribution of ensemble methods is reviewed for various classifiers in [START_REF] Bouziane | Effect of simple ensemble methods on protein secondary structure prediction[END_REF]. Standard deep learning methods do not seem to provide a significant gain with respect to other methods as is shown in [START_REF] Spencer | A deep learning network approach to ab initio protein secondary structure prediction[END_REF], which uses a belief network made of Restricted Boltzman Machines. In contrast, dedicated deep learning network architecture has been recently developed giving better results [START_REF] Wang | Protein secondary structure prediction by using deep learning method[END_REF][START_REF] Wang | Protein secondary structure prediction using deep convolutional neural fields[END_REF]. Studied in [START_REF] Wang | Protein secondary structure prediction using deep convolutional neural fields[END_REF] and available on the server RaptorX [Wang et al., 2016a], DeepCNF (Deep Convolutional Neural Fields) is a mix between a Conditional Random Field (input and output layers) and a deep Convolutional Neural Network. An in-depth analysis of the next required steps in SSP is provided in [START_REF] Yang | Sixty-five years of the long march in protein secondary structure prediction: the final stretch[END_REF]. DeepCNF makes it possible to take into account the correlations between secondary structures at different positions and to look at longer range correlations in protein sequences, which is a crucial point for SSP improvement. Indeed, beta sheets can link distant regions in proteins and it is a severe difficulty for window-based methods (the prediction error rate increases almost linearly with the number of non local contacts in proteins). In the same vein, another study has introduced the architecture LSTM-BRNN (Long Short Term Memory Bidirectional Recurrent Neural Network), and made it available on the server Spider3 with promising results. Another point is to consider meaningful features for SSP, such as intrinsically disordered (so-called chameleon sequences) or semi-disordered regions [START_REF] Zhang | Intrinsically semi-disordered state and its role in induced folding and protein aggregation[END_REF], exposed parts of the protein (greater solvent accessibility in contrast with the hydrophobic core) [START_REF] Faraggi | SPINE X: Improving protein secondary structure prediction by multistep learning coupled with prediction of solvent accessible surface area and backbone torsion angles[END_REF], capping regions (boundaries of helices and sheets) [START_REF] Midic | Improving protein secondarystructure prediction by predicting ends of secondary-structure segments[END_REF] or proline conformation (proline is a particular aminoacid that is responsible for conformational heterogeneity) [START_REF] Song | Prediction of cis/trans isomerization in proteins using psi-blast profiles and secondary structure information[END_REF]. The prediction can also be focused on more detailed secondary structures (8 states) or particular super-secondary structures like beta hairpins (see [START_REF] Xia | Prediction of βhairpins in proteins using physicochemical properties and structure information[END_REF] for an SVM and ensemble-based approach), a motif of two consecutive beta strands that looks like a hairpin and are important in folding kinetics.

Our personal conclusion is that expertise and knowledge has become central to this problem, and it could be interesting to progressively integrate the relations found by a statistical approach in a reasoning framework. Early work along these lines, for instance in Inductive Logic Programming, which achieved wholly satisfactory results when it was proposed [START_REF] Muggleton | Protein secondary structure prediction using logic-based machine learning[END_REF], certainly warrants new studies.

Folding in Space

The next problems after SSP in structural bioinformatics are the prediction of the backbone structure of a protein, which can be represented by a series of values for two angles (dihedral or torsion angles), and the prediction of contacts, typically at a distance < 8 Å. Indeed, SSP provides a rough classification into a few states that lacks precision, particularly at the interface between two secondary structures. A more relevant prediction level for the characterization or the multiple alignment of sequences on 3D structures is the level of local conformational parameters. Important atoms in the backbone of the protein are a central carbon, Cα, attached to the nitrogen N of an amine group, to the carbon C of a carboxyl group, and to a side chain specific to each aminoacid. Angles as well as distances are measured on Cα and sometimes C and N. These problems are much harder than the SSP problem and there is still room for significant improvements. A comparison of methods for predicting dihedral angles of a protein has been proposed in 2014 [START_REF] Singh | Evaluation of protein dihedral angle prediction methods[END_REF], showing the best results for the method SPINE-X [START_REF] Faraggi | Accurate Prediction of One-Dimensional Protein Structure Features Using SPINE-X[END_REF]. This method combines a discrete classifier and continuous real-value prediction of torsion angles trough Conditional Random Fields and is characterized by a six-step training approach that predicts successively the secondary structure, residue solvent accessibility, and torsion angles. The comparison paper also shows that part of the performance of the method is due to a simple representation trick that shifts the angles in order to have an easier separability of the trimodal distributions of angles along the three main SSP states.

Crossing results of multiple predictions of related structural parameters to enhance the prediction of one of them, possibly iteratively, is a general tendency that can be found in state-of-the-art studies [START_REF] Heffernan | Improving prediction of secondary structure, local backbone angles, and solvent accessible surface area of proteins by iterative deep learning[END_REF][START_REF] Li | Deep learning methods for protein torsion angle prediction[END_REF] using deep learning methods. Deep learning allows for easy integration of multiple features and, in this case, recurrent networks and introducing a prediction of the contact number gave the best result. Another interesting recent direction is to discretize (partition) the space of torsion angles into characteristic regions before prediction based on the observation (Ramachandran plot) that there are strong preferences on the possible dihedral angle pairs [START_REF] Gao | Real-value and confidence prediction of protein backbone dihedral angles through a hybrid method of clustering and deep learning[END_REF]. This idea is at the basis of structural alphabets [START_REF] Offmann | Local protein structures[END_REF][START_REF] Pandini | Structural alphabets derived from attractors in conformational space[END_REF], made of a complete set of elementary fragments extracted from the analysis of known structures and sufficient to describe all the conformations of these structures. For instance [START_REF] De Brevern | Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks[END_REF] proposed a structural alphabet of 16 elements describing the conformations of fragments of five residue length, learned in two steps using the principle of Kohonen Self-Organized Maps. Protein backbone reconstruction is achieved by a bayesian probabilistic aprroach, considering sequence windows of size 15. [START_REF] Maupetit | SABBAC: online structural alphabet-based protein backbone reconstruction from alpha-carbon trace[END_REF] proposed Sabbacc, an encoding of the protein trace in a hidden Markov model-derived structural alphabet of 155 elements describing the conformations of fragments of four residue length. Protein backbone reconstruction is achieved by a greedy algorithm assembling the alphabetical fragments in order to minimize an energy-based score.

The most detailed reduced representation of a protein structure is its contact map. A residue contact map is a graph that shows aminoacids with Cβ (the carbon in the side chain attached to Cα) at a distance less than 8 Å in the three-dimensional structure [START_REF] Cheng | Improved residue contact prediction using support vector machines and a large feature set[END_REF]. This information is useful for machine learning since it is invariant to rotations and translations and it helps a lot to retrieve the 3D structure [START_REF] Vendruscolo | Recovery of protein structure from contact maps[END_REF][START_REF] Adhikari | CONFOLD: Residue-residue contact-guided ab initio protein folding[END_REF][START_REF] Pietal | GDFuzz3D: a method for protein 3d structure reconstruction from contact maps, based on a non-euclidean distance function[END_REF][START_REF] Yang | Sixty-five years of the long march in protein secondary structure prediction: the final stretch[END_REF]. Typically, around 5% of residue pairs are in contact in a protein and the number of contacts in a protein is only linear in its length. The Confold method [START_REF] Adhikari | CONFOLD: Residue-residue contact-guided ab initio protein folding[END_REF] uses the iterative scheme described for torsion angle prediction to build a rough 3D model from secondary structures and contacts using a distance geometry algorithm, which then serves as an input to refine the contact and secondary structure prediction and produce a second refined model.

As stated in [START_REF] Wuyun | A large-scale comparative assessment of methods for residue-residue contact prediction[END_REF], most approaches in contact prediction are based on multiple sequence alignment (see section 6) and indices like mutual information between positions in the alignment [START_REF] Dunn | Mutual information without the influence of phylogeny or entropy dramatically improves residue contact prediction[END_REF], since there are strong evolutionary constraints for maintaining the protein structures. Machine learning methods may also be used to predict contacts from features extracted from multiple alignments.

A more recent tendency consists of combining the two types of methods and removing unlikely contact prediction corresponding to indirect coupling pairs obtained by transitivity or adding predictions that are likely to be missed with respect to typical patterns of contacts in proteins [START_REF] Skwark | Improved contact predictions using the recognition of protein like contact patterns[END_REF][START_REF] Jones | Metapsicov: combining coevolution methods for accurate prediction of contacts and long range hydrogen bonding in proteins[END_REF]. [START_REF] Skwark | Improved contact predictions using the recognition of protein like contact patterns[END_REF] presents PconsC2, a pipeline that uses first an ensemble method on 8 multiple alignments and 2 contact prediction methods, then corrects the prediction with deep learning through a 11x11 window providing information about the neighborhood of predicted contacts around each residue pair and a 5-layer feed-forward stack of random forest learners. The same type of approach appears in MetaPSICOV [START_REF] Jones | Metapsicov: combining coevolution methods for accurate prediction of contacts and long range hydrogen bonding in proteins[END_REF], using this time two stages of classic feed-forward networks, the first one learning contact pairs from 672 features extracted from multiple alignments and including an evaluation of the quality of this alignment, and the second one using from among 731 features a window 11x11 matrix of contact pairs predicted by the first stage. Physical constraints that reflect the sparsity of contacts and the presence of particular secondary structures can be added to evolutionary constraints to further reduce the search space. Interestingly enough, a method proposed in [START_REF] Wang | Predicting protein contact map using evolutionary and physical constraints by integer programming[END_REF] first predicts the probability of any two residues forming a contact learning Random Forest built on about 300 features extracted from multiple alignments. In the second stage, it uses integer programming to check a set of hard and soft (that can be relaxed) constraints, trying to maximize the sum of probabilities minus the sum of penalties generated by violated soft constraints.

Among the most recent methods, a qualitative leap has been made in the study [Wang et al., 2017a] by modeling the contact map issue as a pixel-level labeling problem and using a deep learning model concatenating two deep residual neural networks. It simultaneously predicts the label of all entries in the contact matrix. Also far from the state-of-the-art, another recent work [D. [START_REF] Chapman | The evolution of logic circuits for the purpose of protein contact map prediction[END_REF] is interesting because it introduces a particular representation of the contact map prob-lem as learning a logical circuit (deterministic Markov network), whose inputs are binarized features on the sequences and final outputs are a negative and a positive contact decision. The logic gates are elements of a genetic algorithm using point mutation, duplication and deletion as evolutionary operators and accuracy as fitness function. This preliminary work paves the way for more logical approaches to the problem.

Finally, the ultimate and most complex step in structural studies is the prediction of the three-dimensional native structure of proteins. Since the work of Anfinsen in 1973, it is regarded as a free energy minimization problem in a space of possible conformations, a hypothesis that seems to be verified with very few exceptions. This problem is too hard to be solved for most proteins, which have a high number of atoms and a corresponding space that can reach millions of degrees of freedom.

In practice all methods work on so-called "coarse-grained" models, by reducing the number of considered atoms or generating pseudo-atoms abstracting some groups of atoms [START_REF] Blaszczyk | Coarse-Grained Protein Models in Structure Prediction[END_REF]. One must distinguish between the number of degrees of freedom used for the representation of each aminoacid (typically from 1 to 3) and the representation itself. Often, the backbone of Cα atom positions is used as a degree of freedom and the other atoms or pseudo-atoms of the representation calculated from these positions. For instance, the CABS model uses a representation tracing Cα, Cβ , the center of mass of the side chain, and a virtual atom placed at the center of each bond between Cα, the last three values being computed from three consecutive Cα positions. Another interesting but less used possibility, the SI-CHO model, represents a backbone of pseudo-atoms tracing the side chain centers and calculates the Cα positions from three consecutive side chain positions. One of the finest models, Rosetta, represents proteins with 3 dihedral angles for each aminoacid, using a library of low energy backbone-dependent side-chain conformations called rotamers to constrain the set of possible side chains.

All these coarse grain models can be applied to numerous applications in structural biology. It is out of the scope of this chapter to provide a detailed account of all these applications, but we have chosen to present a specific folding abstract framework, called lattice protein folding, that allows us to rapidly test artificial intelligence methods without the need for an in-depth involvement in the physical, chemical and biochemical notions underlying this framework.

The protein folding in lattice models problem Coarse grain models have been developed in many studies within a discretized space, a grid or more generally a lattice [START_REF] Mann | Exact methods for lattice protein models[END_REF]. The lattice folding issue consists in finding a path of minimal score in the lattice such that (a) each residue is restricted to be placed on vertices of a lattice; b) each vertex is associated with at most one residue (self-avoiding walks); and c) a residue has to be placed in the neighborhood of the previous residue in the protein, this neighborhood being defined by a set of predetermined vectors. The cost function is generally derived from considerations on the free energy of the resulting molecule but is much simpler to compute than in continuous models. We are pointing to two types of lattice that are representative of the variety of models, the first one having been extensively studied:

The HP lattice: One of the simplest models of protein folding is the hydrophobic-hydrophilic (HP) model, which abstracts aminoacids in simply two states, hydrophobic (H, nonpolar) or hydrophilic (P, polar) and places them on a 2D square or a 3D cubic lattice. The score (energy function) is simply based on hydrophobicity: it is typically the number of nonbonding H in contact. High-resolution lattices: Some authors argue that the main factor responsible for an observed folding are the constraints between side chains. For this reason, the SICHO model has been developed, taking the side chains as vertices and including a high number of possible interactions between these side chains [START_REF] Feig | Accurate reconstruction of all-atom protein representations from side-chain-based lowresolution models[END_REF]. The CABS lattice is the most refined lattice that has been proposed [START_REF] Koliński | Protein modeling and structure prediction with a reduced representation[END_REF]. It has 3 interaction centers for each amino acid and a basis of 800 vectors for the Cα neighborhood.

A number of lattice models have been proposed that can represent more or less finely the natural folding of proteins, in particular with respect to secondary structures. Among the main difficulties of the search is the detection of symmetries leading to equivalent conformations [START_REF] Gan | A symmetryfree subspace for ab initio protein folding simulations[END_REF]. Even in this simplest case, the problem is known to be NP-complete [START_REF] Berger | Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete[END_REF]]. Approximation algorithms exist however and folding in the cubic lattice may be achieved in linear time, for instance with an approximation ratio of 3/8 [START_REF] Newman | Combinatorial problems on strings with applications to protein folding[END_REF]. A variety of local search methods have been tried as well as constraint methods (see Chapter 6 of Volume 2), which have proven to be very interesting in this respect [START_REF] Backofen | A constraint-based approach to fast and exact structure prediction in three-dimensional protein models[END_REF][START_REF] Mann | CPSP-tools-exact and complete algorithms for high-throughput 3d lattice protein studies[END_REF]. A description of exact methods may be found in the review [START_REF] Mann | Exact methods for lattice protein models[END_REF]. Many variants of the HP model exist that enable for instance diagonals (triangular lattice), work in an hexagonal lattice [START_REF] Shaw | Protein folding in HP model on hexagonal lattices with diagonals[END_REF] or in a face-centered cubic lattice (fcc, one of the best models in this category [START_REF] Pokarowski | A minimal physically realistic protein-like lattice model: designing an energy landscape that ensures all-or-none folding to a unique native state[END_REF][START_REF] Shatabda | Constraint-based evolutionary local search for protein structures with secondary motifs[END_REF]). Other moderate resolution lattices exist, using a larger basis of vectors for the definition of the neighborhood. For instance, the "chess knight" model in 3D uses vectors (±2, ±1, 0). The 210 and 310 models use respectively 56 and 90 vectors.

Despite being one of the oldest models, the HP model continues to appear regularly in literature. For instance, in [START_REF] Dogan | A novel state space representation for the solution of 2D-HP protein folding problem using reinforcement learning methods[END_REF] the problem is stated as a robot path planning problem where each amino-acid in the sequence is consecutively added to form continuous and self-avoiding amino-acid chains on the lattice. A new reinforcement learning method is applied to this planning problem where such methods are known to perform well (see Chapter 12 of Volume 1). Authors use for this purpose a compact state space representation and a distributed Q-learning algorithm (Ant-Q). In [START_REF] Dubey | Protein structure prediction on 2d square hp lattice with revised fitness function[END_REF], the authors propose an enhanced en-ergy function for the square lattice model taking into account other interactions than H-H ones. A mixed integer programming formulation is presented in [START_REF] Yanev | Protein Folding Prediction in a Cubic Lattice in Hydrophobic-Polar Model[END_REF], together with an exact algorithm and two heuristic algorithms. A swarm optimization algorithm and a Tabu search are combined in [START_REF] Guo | Hybrid method to solve HP model on 3D lattice and to probe protein stability upon amino acid mutations[END_REF]. For a review of constraint programming in structural bioinformatics, see [START_REF] Barahona | Constraint programming in structural bioinformatics[END_REF]. Due to its complexity, the CABS model is closer to the continuous dynamic approaches. It can only be used in integrated environments that are predicting various structural properties like the presence of secondary structures and produce the corresponding constraints to restrain the general model [START_REF] Blaszczyk | CABS-fold: server for the de novo and consensus-based prediction of protein structure[END_REF][START_REF] Gront | High throughput method for protein structure prediction[END_REF].

We conclude this section by mentioning other important applications and point to some artificial intelligence techniques applied in this field.

The homology modeling of protein structure and the protein threading problem look both for the alignment of a protein sequence (the target) on a protein structure (the template). The first method, as in the case of sequence-sequence alignments, uses an homologous protein of known structure for the template. Protein threading deals with the harder case where there is no hypothesis of the existence of a homologous protein. In this case, one relies on the fact that the number of natural foldings is very limited and that a library of core templates is available, usually consisting of a set of segments separated by fixed or variable lengths. For each template, the best alignment is obtained by optimizing an objective function scoring the compatibility between sequences and between positions in the template. The complexity of the problem depends on the chosen structural model and the amount of homologous sequences available. Finding the optimal alignment is NP-hard in the general case where there are gaps of varying length between the segments, and where the objective function includes interactions between neighboring amino acids in the structure. Many methods are based on extensions of the dynamic programming approach used for sequence alignment, adding constraints from knowledge on amino-acid preferences with respect to neighbors, mutations, solvent accessibility or secondary structures for instance. A typical program of protein threading is RaptorX [START_REF] Peng | Low-homology protein threading[END_REF], which uses a collection of regression trees to determine the scoring function of each alignment state in a Conditional Random Fields model that predict the state (match or gap) of each position in the alignment, and uses a neural network to rank the different alignments on the target and give a measure of quality for each alignment [START_REF] Källberg | Template-based protein structure modeling using the raptorx web server[END_REF].

The protein docking problem is a 3D matching problem: it entails finding minimal free energy conformations of a protein complex made of a protein receptor and a generally small molecule (a drug) called ligand or another protein. As in the previous problems, an efficient approach is template-based modeling, which uses the knowledge of an already known complex to guide the conformation search of the new complex [START_REF] Xue | Template-based protein-protein docking exploiting pairwise interfacial residue restraints[END_REF]. For instance, case-based reasoning (see Chapter 10 of Volume 1) has been used in [START_REF] Ghoorah | Protein docking using case-based reasoning[END_REF] for this problem.

The protein folding pathway prediction problem looks at the analysis of the folding kinetics of a protein with a known 3D structure. It has been represented by roadmaps, which are graphs of conformations where each edge indicates a possible transition between conformations [START_REF] Moll | Roadmap methods for protein folding[END_REF]. Roadmap-based methods were originally developed in robotics for collision-free robot motion planning and vastly extended and adapted for folding.

Finally, computational protein design is the process of designing new protein sequences with a fold close to a target protein structure. The ultimate goal is protein engineering, i.e., the design of new molecules adapted to target new materials or new functions, like for instance enzymes that are critical components in bioengineering and biomedical applications [START_REF] Coluzza | Computational protein design: a review[END_REF]. Rational protein design makes massive use of libraries of rotamers and can be seen as an optimization problem based on complex energy functions. In this domain, the exact solving method at the basis of many developments is a special dominance search algorithm (dead-end elimination), followed by an A* algorithm. Linear Programming, Quadratic Programming, Weighted Partial MaxSAT and Graphical Model optimization can be used to solve this problem, but a special form of Weighted Constraint Satisfaction formulation (Cost Function Network, see Chapter 7 of Volume 2) proves to be very efficient for this task [START_REF] Allouche | Computational protein design as an optimization problem[END_REF][START_REF] Traoré | Fast search algorithms for computational protein design[END_REF] .

Network Modelling

As emphasized in a recent editorial of a special issue of PLOS Computational Biology on biological networks [START_REF] Ideker | Network approaches and applications in biology[END_REF], networks are everywhere in biology from molecular interaction circuits or modules to ecosystems, and have become a major mode of analysis in bioinformatics studies. Networks make it possible to understand biological entities at the system level, explaining diseases or drug effects as a cumulative result of small effects of individual genes of a cell for instance. This global understanding is out of reach of scientists from the mere observation of components for relatively small systems due to non linearity/additivity of regulations or interactions and it is even harder in current developments, which are designed to model genome-scale systems. It is thus crucial to assist biologists in this task not only through the development of simulators, but also for the analysis of a network behavior in plain intelligible language, i.e., is by checking properties and finding causal explanations.

At a higher level of organization, the interactions within bacterial consortia or in host-microbial symbiosis are and will certainly be the subject of a growing number of studies. Networks are present as observed data and as an abstract graph data structure (associated with a set of dedicated methods) that represent physical structures, as well as the dynamics of living components. If one considers the kinetics of components, the time scale may vary a lot depending of the type of interaction. For instance, it can range from milliseconds to seconds between the first and last stages of a signaling cascade (activation pathway from cell surface receptors to molecules controlling a cell function such as cell division) from seconds to minutes for metabolic reactions (biochemical reactions occurring in a cell) and reach hours for regulation processes (e.g. cell mechanisms used to increase or decrease the production of specific gene products). Signaling, regulation and metabolic networks are the three main types of networks studied in cells.

The representation of networks has used many formalisms that may be characterized as discrete (qualitative) or continuous models. A broad review of the work in this area can be found in the next chapter (see Chapter 8 of this volume). We will focus here on discrete modeling since artificial intelligence methods are more directly applicable in this case. The early works of R. Thomas S. Kauffman in the 1970's have have demonstrated the value of logical modeling for representing gene regulation mechanisms in cells, by seeing them as discrete dynamical systems. The gene expression levels may be abstracted using Boolean variables (e.g. active or not active), time using logical steps and the expression changes using logical functions over the set of interacting genes. This simple but powerful framework is formalized in the following definition: Definition 1. Boolean Networks are made of a graph G = {g i , i = 1, n} of Boolean variables. An edge e i j ∈ G represents the fact that variable g i is one of the inputs to variable g j . Each node is associated with a logical formula (a transition function) giving the output value of its Boolean variable with respect to the value of its input variables. A state is a vector of values over the complete set of variables. The state transition graph (STG) is the graph of all possible transitions between states, based on an update rule. Using formulas attached to variables to compute their new value, two main update rules are used in practice: the synchronous rule, which updates all variables simultaneously, and the asynchronous rule, which updates one variable at a time.

It is possible to extend this framework to multi-valued variables in order to take into account the possibility of multiple thresholds.

Numerous studies have used this formalism on biological applications. Several reviews are available on this topic [START_REF] Albert | Boolean modeling: a logic-based dynamic approach for understanding signaling and regulatory networks and for making useful predictions[END_REF][START_REF] Abou-Jaoudé | Logical modeling and dynamical analysis of cellular networks[END_REF] and on modeling the dynamics of cellular networks [START_REF] Le Novere | Quantitative and logic modelling of gene and molecular networks[END_REF]. Some repositories are emerging on the web ( [START_REF] Chelliah | BioModels: ten-year anniversary[END_REF][START_REF] Klarner | Pyboolnet: a python package for the generation, analysis and visualization of boolean networks[END_REF]) and an informal consortium, CoLoMoTo (Consortium for Logical Models and Tools) [START_REF] Abou-Jaoudé | Logical modeling and dynamical analysis of cellular networks[END_REF] is working on the definition of standards.

The extraction of networks from scientific literature has already been mentioned in section 2. It is also possible to automatically refine such an initial prior knowledge network using experimental data, such as gene expression data for gene regulation networks [START_REF] Lim | Btr: training asynchronous Boolean models using singlecell expression data[END_REF] or phosphoproteomics data for signaling networks [START_REF] Videla | Learning Boolean logic models of signaling networks with ASP[END_REF]. The first paper uses a form of swarming hill climbing strategy, whereas the second one produces all possible solutions through a combinatorial approach code in Answer Set Programming (ASP). For metabolic networks, the reconstruction of the set of biochemical reactions in a newly sequenced organism can be inferred from the sequenced and annotated genomes [START_REF] Karpe | The pathway tools pathway prediction algorithm[END_REF]. It works by recognizing in the new genome the enzymes catalyzing each reactions, then using the knowledge of previously known pathways from other organisms. To predict unknown or alternative pathways, it is possible to reason on atomic transfers [START_REF] Boyer | Ab initio reconstruction of metabolic pathways[END_REF].

Once constructed, the metabolic network is usually too large to be analyzed directly. A general technique to reduce it is based on the description of the properties that one wishes to keep between the initial network and the reduced network and then to automatically infer the minimum possible reduced network. This was proposed in [START_REF] Röhl | A mixed-integer linear programming approach to the reduction of genome-scale metabolic networks[END_REF], where the authors developed a mixed-integer linear programming (MILP) approach for computing this reduction.

The analysis of networks may be achieved from a topologic, static point of view, or from a kinetics-centered, dynamic, point of view.

In metabolic networks, static analysis includes the search for two close concepts, elementary modes and minimal cut sets [START_REF] Acuna | Modes and cuts in metabolic networks: Complexity and algorithms[END_REF].

Elementary flux modes (EFMs) analyze networks from a pathway-oriented perspective. They are the minimal sub-networks (with respect to set inclusion of reactions) that can function (stoichiometrically and thermodynamically feasible) in steady state. These modes can help reveal the capabilities/objectives of a cell metabolic network, that is, the matching between phenotype and genotype. The standard approach to solve this problem is to reduce it to the enumeration of extremal rays in a pointed polyhedral cone, a standard problem in computational geometry. Unfortunately, the number of EFMs can increase exponentially with the network size. An interesting question is then how to navigate into the solution space instead of enumerating the solutions. To this end, the authors of [START_REF] Martin | Minimality of Metabolic Flux Modes under Boolean Regulation Constraints[END_REF] allow the user to add/remove boolean constraints on the solutions that interest them. They use then a Satisfiability modulo Theory solver, CDC4, to solve both the boolean constraints on reactions occurring in the solutions and linear constraints taking into account stoichiometric data and steady state fluxes.

A minimal cut set (MCS) is a minimal (irreducible) set of reactions in the network whose inactivation will definitely lead to a failure in certain network functions (see the paragraph on perturbation analysis at the end of this section) [START_REF] Klamt | Generalized concept of minimal cut sets in biochemical networks[END_REF]. It helps to identify crucial, fragile parts in the network structure and to select suitable targets for repressing undesired metabolic functions.

Studying the dynamics of a given Boolean network entails three main issues on the associated state transition graph ST G = (S, T ):

The state transition graph search problem

Attractors: Find all minimal subsets of states A ⊆ S that are trap domains, i. e., such that the transition from an element of A yields an element of A. As an important particular case, stable or steady states are attractors reduced to a singleton and do not depend on the update scheme. The others are called cyclic attractors. The detection of stable or cyclic attractors is NP-hard [START_REF] Akutsu | Finding a periodic attractor of a Boolean network[END_REF]. Reachability: Check the absence/presence of specified trajectories in ST G, i.e., such that there are paths in ST G whose elements s i belong to a specified subset S i of S. Perturbation analysis: Check the effect of fixing some variable values or some logical function values on the attractors and reachability properties.

Stable state atractors have been shown to correspond to identified cell differentiation states, a good example being the study of the regulatory and signaling networks associated with Th-cell subtypes differentiation [START_REF] Naldi | Diversity and plasticity of th cell types predicted from regulatory network modelling[END_REF]. Cyclic attractors have been shown in the cell cycle networks of Yeast or Mammals (see e.g. [START_REF] Barberis | Advances and challenges in logical modeling of cell cycle regulation: perspective for multi-scale, integrative yeast cell models[END_REF][START_REF] Traynard | Logical model specification aided by model-checking techniques: application to the mammalian cell cycle regulation[END_REF]). Attractors provide, more generally speaking, pointers to the possible steady functioning modes of the studied systems, either in normal conditions or under degraded conditions. They are also a way of checking the quality of a model by comparing attractors with the observed behavior of the biological system.

The detection of stable or cyclic attractors is NP-hard [START_REF] Akutsu | Finding a periodic attractor of a Boolean network[END_REF]. A number of algorithms have been proposed to find attractors of a Boolean network, mostly using (reduced-order) binary decision diagrams. Quite naturally, a SAT-based bounded model checking method has been experimented in the case of synchronous networks [START_REF] Dubrova | A SAT-based algorithm for finding attractors in synchronous Boolean networks[END_REF]. Basically, the idea is to search by unfolding the transition relation for paths of bounded length p in the STG, to increase p if there is a path that is not a circuit and to mark the variables that are part of a circuit as attractors and exclude them from possible paths.

In practice, the knowledge of the formula associated with each gene and of the update scheme may be incomplete. The system ASP-G [START_REF] Mushthofa | ASP-G: an ASP-based method for finding attractors in genetic regulatory networks[END_REF]] uses a higher level language for describing the network and the update scheme (with predicates such as activates, inhibited or changed) and relies on Answer Set Programming solvers to search efficiently the STG based on the previous SAT-based approach. The authors use incremental solving on the path length and, once a solution is found, the attractor is removed from the search space by adding a new constraint. In [START_REF] Abdallah | ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks[END_REF], ASP is also used for more ambitious work extended to both synchronous and asynchronous update modes and considering automata networks instead of Boolean networks, a framework that enables multivalued domains for variables and where more sophisticated update rules like nondeterministic synchronous mode can be introduced. In its current state, the program works in incremental mode (looking for paths of fixed size) and can produce several times the same attractor described by several cycles.

Another interesting approach [START_REF] Klarner | Computing maximal and minimal trap spaces of Boolean networks[END_REF] looks at minimal and maximal trap domains represented by partial states (with free variables) instead of attrac-tors and computes them efficiently from the set of prime implicants of the Boolean formulas. An insightful paper by K. Inoue has established a deeper relationship between Boolean networks and Logic programs [START_REF] Inoue | Logic programming for Boolean networks[END_REF] (Logic programming is described in Chapter 4 of Volume 2). Stable sates of a network may indeed be characterized as supported models of the corresponding logic program, a correspondence that allows a trivial coding of their search.

The reachability problem is basically searching trajectories in a state transition graph of size 2 n , where n is the number of Boolean variables and is a perfect application field for model checking and temporal logics. All studies in this field formalize this graph with a finite state transition system (FSTS) that is easily mapped into a Kripke structure. This framework is very general and can be applied far beyond the case of Boolean networks. In the field of biological systems, fine simulation of their dynamics by piecewise linear differential equations can, in particular, be considered. The principle is to associate with states hyper-rectangles in the concentration space [START_REF] Batt | Symbolic reachability analysis of genetic regulatory networks using discrete abstractions[END_REF] and a tool like GNA allows us to generate and export the FST S from differential models [START_REF] Batt | Genetic Network Analyzer: A Tool for the Qualitative Modeling and Simulation of Bacterial Regulatory Networks[END_REF]. See [START_REF] Carrillo | An overview of existing modeling tools making use of model checking in the analysis of biochemical networks[END_REF][START_REF] Brim | Model checking of biological systems[END_REF] for reviews of existing tools. Once discretized, the state space can be explored via a logic allowing branching time (states with more than one immediate future) like CTL (Computational Tree Logic) or the µ-calculus, a practical issue being that it helps biologists to formulate their questions. This generic question in model checking has been addressed in [START_REF] Monteiro | Temporal logic patterns for querying dynamic models of cellular interaction networks[END_REF] through the development of a specific language of patterns with place-holders that allows the use of predefined state descriptors (e.g. increases or isSteadyState) and predefined types of questions (e.g. possibility of occurrence of a pattern or if-then statements). Specialized model checkers have been developed for the study of genetic regulation networks such as Antelope [START_REF] Arellano | Antelope": a hybrid-logic model checker for branching-time Boolean GRN analysis[END_REF], which addresses the important question of not just checking but exhibiting the states with a given property, using a Hybrid CTL with state variables. The size of the state space remains a crucial parameter for model checkers and the current state of the art is still too limited to query all the known models.

The third problem on Boolean networks, perturbation analysis, has been mainly applied to Probabilistic Boolean Networks, a stochastic extension of the standard framework where the transition function is replaced by a set of possible functions with an associated probability distribution. One of the main objectives of the analysis is focused on intervening in biological cell dynamics in order to alter the gene regulatory network or the signaling network and avoid undesirable cellular states, particularly in the search for a therapeutic strategy (e.g. to counteract the development of cancerous cells). The difficulty is how to bypass the inherent living system's robustness that uses many redundant pathways, while avoiding side effects and thus looking to minimize the necessary changes. Finding an optimal control strategy leading to a desired state by changing some variable values is NP-hard [START_REF] Akutsu | Control of boolean networks: Hardness results and algorithms for tree structured networks[END_REF]. It is also possible to act on the transition functions by altering the transition probabilities or flipping a minimum number of values in the truth table [START_REF] Xiao | The impact of function perturbations in Boolean networks[END_REF]. People are often using quantitative approaches to solve this problem by finely tuning the system's kinetic behavior and the use of Artificial Intelligence techniques on this problem is less well developed. The problem has been set within a three-valued logical framework (to represent knock-out, knock-in and no intervention operations) in [START_REF] Samaga | Computing combinatorial intervention strategies and failure modes in signaling networks[END_REF]. It defines intervention problems made of a set of pairs (G,C), where G is a goal made of desired values for some target species (e.g. genes or reactions) and C equates to environment constraints setting some other species to fixed values. The issue is then to find (subset-)minimal intervention sets (MIS), i.e., a set of values for a set of species S such that all goals G are satisfied in their context C and at least one goal is not satisfied if an element of S is removed. The authors introduce a dedicated breadth-first search algorithm and emphasize the importance of preprocessing to reduce the dimension of a practical problem by finding classes of equivalence containing interventions having the same effect on target species. An ASP encoding is proposed in [START_REF] Kaminski | Minimal intervention strategies in logical signaling networks with ASP[END_REF] to enumerate all MIS for real-world signaling networks, showing that negation by default and recursive definition of reachability are valuable tools for searching for larger intervention sets and potentially solving the unbounded problem where the size of the intervention sets is not bounded. In practice, the ideal network is not known and it would be interesting to look for solutions that are compatible with several alternative networks explaining the same system.

Apart from signaling networks, metabolic networks have also been studied from the point of view of control, the interventions consisting of deleting reactions and/or regulating the reaction fluxes. One of the main industrial opportunities of such control is the optimized production of some target compounds by microbial organisms, a process called metabolic engineering, which is a research axis of synthetic biology. The MIS problem is transformed into a very similar Minimal Cut Set problem (MCS) [START_REF] Von Kamp | Enumeration of smallest intervention strategies in genome-scale metabolic networks[END_REF] or Regulatory MCS (RegMCS) [START_REF] Mahadevan | Genome-scale strain designs based on regulatory minimal cut sets[END_REF] and Mixed Integer Linear Programming models have been reported in these publications in relation to solving MCS and RegMCS.

In contrast to the previous problem, the use of perturbations to learn the network has been the subject of many publications. Very few studies address both problems, one exception being the toolbox caspo [START_REF] Videla | caspo: a toolbox for automated reasoning on the response of logical signaling networks families[END_REF], which proposes functions dedicated to each problem.

Understanding Evolution

The study of evolution is certainly a main topic of interest for biologists and bioinformatics has had a huge impact in this field since the advent of sequencing techniques. It is not merely of interest to evolutionary biologists and for the study of biodiversity: evolution is a fundamental mechanism that helps to solve hard problems and obtain reliable answers at the level of populations but also in respect of structural or functional biological issues. It is thus also a key issue for bioinformatics. The term Evolution refers essentially in biology to changes in the inheritable traits of populations which occur over generations. Since easy access to the molecular content of living things, evolution can be considered at a much finer level than before, and evolution can even be observed at the individual level. A particularly important recent application relates to the evolutionary process in cancer. A tumor is an evolutionary process. It starts from a single cell and evolves with an anarchic development, including somatic mutations. Technology allows us now to sample a tumor and try to retrieve the history of tumoral cells, a combinatorial problem that may be treated by a phylogenetic approach [START_REF] Popic | Fast and scalable inference of multi-sample cancer lineages[END_REF][START_REF] Malikic | Clonality inference in multiple tumor samples using phylogeny[END_REF][START_REF] Caravagna | Algorithmic methods to infer the evolutionary trajectories in cancer progression[END_REF][START_REF] Schwartz | The evolution of tumour phylogenetics: principles and practice[END_REF].

The most cited papers in all research fields, as stated in news published in the journal Nature in 2014 on the top 100 papers cited since 1900, are, together with the Sangers Sequencing method and amplification methods, two papers on phylogenetics and two programs in this field. Moreover, phylogeny makes extensive use of sequence comparison and programs in this field are well represented with two versions of Blast and two versions of Clustal being cited (the multiple sequence alignment method on ClustalW is ranked 10th). It is why we start this section with a description of multiple alignment.

Multiple Sequence Alignment

At the core of many problems involving sequences in biology (sequence assembly, functional or structural annotation, homology search and phylogeny) lies the issue of sequence alignment. Its goal is to line up the letters in several sequences in order to exhibit a maximal similarity between letters at the same position. It may concern protein, DNA or RNA sequences, which are under a selective pressure. Indeed, this problem stems from the fact that all species originate from a common ancestor: sequences are assumed to be on the leaves of some unknown common evolutionary tree and thus share common characteristics that have become blurred by various mutation and insertion/deletion events. This is the reason why multiple sequence alignment and phylogeny are closely related, although other aspects like structural or functional properties may be taken into account. An alignment of a set of sequences helps to recover the evolutionary tree of the species they come from and, conversely, a known or assumed evolutionary tree (the guide-tree) helps to recover a relevant alignment of sequences. In fact, a growing number of authors are trying to build sequence alignment and phylogeny simultaneously [START_REF] Ng | A Fast Algorithm for Reconstructing Multiple Sequence Alignment and Phylogeny Simultaneously[END_REF]. Note that the issue of sequence conservation modeling is not reduced to multiple alignment. If one is interested in sequence annotation or functional prediction, multiple alignment can usefully be extended to a pattern recognition problem (HMM profile) or even to grammatical inference studies (automata), working with a more expressive syntactic model of conservation [START_REF] Coste | Learning the Language of Biological Sequences[END_REF]. Moreover, multiple alignment takes into account evolution events such as point mutations, insertions and deletions, but more complex events can occur in a genome such as duplications, inversions, or recombinations, and there is still a lot of work to be done to address all these sources of variability.

Formally speaking, the Multiple Sequence Alignment (MSA) issue is as follows:

Definition 2. Given a set of sequences S = s 1 , ..., s n on a finite alphabet Σ , an MSA of S is a set of sequences A = {a 1 , ..., a n } on Σ ∪ {" -"}, where " -" is a new letter representing insertion/deletion events (gaps) in the aligned sequences. Moreover, all elements of A have the same length and all a i are equal to s i up to the deletion of the " -" characters. Given a cost or score function c on pairs of sequences in an MSA, the MSA issue looks for an MSA A optimizing the value of a function of c.

A frequent choice in this general definition is the Sum of Pairs criterion (SP) that minimizes the sum Σ i< j c(a i , a j ), where c is typically defined as a sum along the alignment positions of a scoring of letters at these positions and the gaps receive a special treatment with an affine function. In this setting and its variants, MSA is an NP-complete problem and, for this reason, using a standard dynamic programming approach provides an exact solution in practice only for a very small number of sequences, typically no more than 3. Artificial intelligence took an early interest in this problem since it can be reduced to finding a shortest path in a huge graph joining the possible alignment positions of characters in each sequence and a branch and bound algorithm can be applied [START_REF] Gupta | Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment[END_REF]. Variants of the A* algorithm (see Chapter 1 of Volume 2) have been developed by Ikeda et al. and Yoshizumi et al. both for the exact and the approximated case [START_REF] Ikeda | Enhanced A* algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases[END_REF][START_REF] Yoshizumi | A* with partial expansion for large branching factor problems[END_REF]. This gave rise to a number of papers on space-efficient or faster heuristics [START_REF] Zhou | Space-efficient memory-based heuristics[END_REF][START_REF] Korf | Frontier search[END_REF][START_REF] Schroedl | An improved search algorithm for optimal multiple-sequence alignment[END_REF], or the recursive best first search MREC enabling the exact optimal alignment of up to 11 sequences [START_REF] Koshino | Applying the various optimal solution search methods to multiple sequence alignments and performance evaluation[END_REF]. Recent works are focusing on solutions using external disk space, adapted to the best first search order, and multi-threaded computation [START_REF] Hatem | External Memory Best-First Search for Multiple SequenceAlignment[END_REF][START_REF] Sundfeld | Pa-star: A disk-assisted parallel a-star strategy with locality-sensitive hash for multiple sequence alignment[END_REF], pushing further the limits of exact methods.

A number of suboptimal approaches have been developed and are still to be developed, for instance to scale to large sets of sequences (million) or large sequences (whole genomes). A basis of almost all these approaches is the use of a progressive strategy, starting from pairwise alignments and trying to combine them in the best ordering. Following the works of Korostensky and Gonnet, it is possible to define the progressive alignment using a circular sum measure where each sequence is aligned with exactly two sequences [START_REF] Korostensky | Near optimal multiple sequence alignments using a traveling salesman problem approach[END_REF][START_REF] Gonnet | Evaluation measures of multiple sequence alignments[END_REF]. Multiple alignment is reduced this way to a Traveling Salesman Problem, where the goal is to find the circular ordering of sequences minimizing the sum. Although this approach has some relevance with respect to evolution, it appears to have not been pursued apart from a small piece of work in [START_REF] Abu-Srhan | A hybrid algorithm using a genetic algorithm and cuckoo search algorithm to solve the traveling salesman problem and its application to multiple sequence alignment[END_REF]. The progressive strategy is often combined with an iterative strategy, where solutions are progressively refined in order to improve the alignment. Stochastic optimization is useful in this case. In [START_REF] Omar | Multiple sequence alignment using optimization algorithms[END_REF], a genetic algorithm is used for the pro-gressive part and a simulated annealing algorithm is used for the iterative part. Many aligners have been developed but none outperforms the other in all cases, depending on the properties of sequences (presence of domains, partial sequences, intrinsically unstructured regions, alternatively regions with known 2D/3D structure, etc.). A natural approach is then to propose meta-methods running a number of algorithms in parallel and choosing the best alignment in the different results [START_REF] Muller | Aqua: automated quality improvement for multiple sequence alignments[END_REF]. More recently, the concept of assisted multiple alignment has emerged as an important issue for more efficient and more relevant alignments. AlexSys is an expert system in protein multiple sequence alignment that learns rules predicting for each method if it is suited or not to the sequences to be aligned [START_REF] Aniba | Alexsys: a knowledge-based expert system for multiple sequence alignment construction and analysis[END_REF].

Building Phylogenetic Trees

Given a set of species (or taxonomic units), each one being usually represented by a subset of its gene sequences, molecular phylogenetic studies try to infer a phylogenetic tree that reflects the actual lineages of species during evolution. Multiple alignments are just one (important) source of data for building phylogenetic trees. Numerous other sources of information are used to build, compare and reconcile trees. The following definition is adapted from [START_REF] Brooks | Inferring phylogenetic trees using answer set programming[END_REF][START_REF] Erdem | Applications of Answer Set Programming in Phylogenetic Systematics[END_REF][START_REF] Miranda | Inferring phylogenetic trees using pseudo-Boolean optimization[END_REF] Definition 3. A phylogeny is a septuple P = V, E, F,C, D C , v, L , where (V, E) is a graph commonly describing a rooted binary tree, F is the set of terminal nodes of the graph (leaves of the tree), C is a set of qualitative attributes, the characters, with domains D C , v is a function giving the value of each attribute for each terminal node in F, and L is an optional function that provides a real length for each edge. Variants exist with unrooted trees, non binary trees, or even phylogenetic networks that take into account the possibility of a reticulate evolution due to the exchange of genes between species (horizontal transfer).

The characters may be binary and, moreover, cladistic (the values are ordered during evolution from an ancestral state to derived states). When data are made of genetic sequences, characters are positions in a multiple alignment with at least two different letters (called SNPs). These mutation positions are generally binary characters. Nodes of the tree may be considered as states of the evolution process and edges as transformations, such as mutations. Considering only its structure (without function L ), a general problem is to build a tree on a set of species that is correct with respect to a given set of characters.

The phylogeny inference problem Given a set F of taxonomic units and a triple C, D C , v providing character values for each element in F, decide if there exists a phylogeny that fulfills one of these criteria:

• k-compatibility: at least k characters must be compatible with the tree. A character is compatible with a phylogeny tree if the set of all vertices having the same value for this character forms a subtree. • k-parsimony: the tree may be mapped to a rectilinear Steiner tree with a size at most k. In such a tree, edges have an integer length that is positive or zero. The paths between two elements of F have a length that equals the Manhattan distance between the vectors of their characters. • d-goodness-of-fit: Assumes the analysis of characters to be summarized with a symmetric dissimilarity matrix D between pairs of elements of F.

The tree must have a goodness-of-fit at least d with respect to D. Given a phylogenetic tree with a function L associating a value with each of its edges, it is possible to build a symmetric matrix P giving the path length between pairs of elements of F. The goodness-of-fit is the Euclidean distance between P and D (i.e. the Frobenius norm of the difference of the two matrices).

All these problems and variants have been proved NP-complete by Day and Sankoff. Apart from the decision problems, people often look for optimization versions, for instance looking for a tree with a maximum number of compatible characters. A topological criterion may also be used to build the tree from unrooted trees produced on subsets of taxonomic units, typically quartets of species.

The whole setting may be a bit more complex since a number of assumptions have to be added to obtain realistic trees, the main one being about the evolution of characters.

In a tree, starting from a state where all characters are considered absent, a character may be gained once and for all (perfect phylogeny), gained once and then lost at most once (persistent phylogeny), gained several times but never lost (Camin-Sokal criterion), etc. Constraint modeling frameworks can adjust with great flexibility to these many different criteria. Integer Linear Programming has been successful in providing different models, depending on the type of data to be processed [START_REF] Sridhar | Mixed integer linear programming for maximum-parsimony phylogeny inference[END_REF] (perfect phylogenies, maximum parsimony), [START_REF] El-Kebir | Reconstruction of clonal trees and tumor composition from multi-sample sequencing data[END_REF] (perfect phylogenies from tumor multisample sequences), [START_REF] Gusfield | Persistent Phylogeny: A Galled-tree and Integer Linear Programming Approach[END_REF] (persistent phylogenies), [START_REF] Bonizzoni | Beyond Perfect Phylogeny: Multisample phylogeny reconstruction via ILP[END_REF] (incomplete perfect phylogenies on tumoral sequences). Answer set programming has been used in [START_REF] Brooks | Inferring phylogenetic trees using answer set programming[END_REF] (perfect phylogenies), [START_REF] Kavanagh | Constructing Camin-Sokal Phylogenies Via Answer Set Programming[END_REF] (Camin-Sokal criterion) and [START_REF] Wu | Quartet-based phylogeny reconstruction with answer set programming[END_REF] (maximum quartet consistency).

In practice, even with these assumptions, a number of equivalent solutions may exist and it is fundamental to put the experts in the decision loop. This is why in recent years algorithmics is not the sole concern of evolutionary bioinformatics. There is a growing interest in a knowledge-based approach in this field since it brings together a large community and many results that may be partially contradictory have to be integrated. The ability to build complex queries and check combinatorial prop-erties has shed light on logical approaches. In particular, if one considers a phylogenetic tree as a transition system (by adding loops on the leaves), it is possible to apply a temporal logic to make queries on the tree properties, the state properties or a mix of both. [START_REF] Requeno | Temporal logics for phylogenetic analysis via model checking[END_REF] have thus developed a model checking framework where it is possible to use CTL on phylogenetic trees. The possibility to obtain not only verifications but also counter-examples if formulas are not satisfied is important in a practical interactive context where the user makes an intensive use of queries to mine the trees (e.g. checking if there are back mutations in the tree can be used to detect these mutational events). This framework has been extended to the treatment of quantitative information through the use of stochastic logics [START_REF] Requeno | Evaluation of properties over phylogenetic trees using stochastic logics[END_REF]. This allows to introduce in queries some probabilities and an explicit time. It is of significant interest if one wants to test models of evolution and to compute maximum likelihood estimations for trees in this context.

Other logical frameworks such as Answer Set Programming have been used. For instance, the supertree construction problem, which consists of building a tree that is maximally consistent with a set of trees built on overlapping sets of species, has been encoded as an ASP model in [START_REF] Koponen | Optimizing phylogenetic supertrees using answer set programming[END_REF]. A web service interface API has been developed in ASP for TreeBASE, a relational database designed to manage and explore information on phylogenetic relationships [START_REF] Le | ASP at Work: An ASP Implementation of PhyloWS[END_REF] and a toolkit has been developed for the alignment, consistency checking and inconsistency repair of taxonomies, using various reasoning systems (first order, Answer Set and dedicated provers) [START_REF] Chen | Euler/X:A toolkit for logic-based taxonomy integration[END_REF][START_REF] Franz | Reasoning over taxonomic change: ExploringAlignments for the perelleschus use case[END_REF]. Note that the alignment of trees may be used to build a phylogeny with a divide and conquer approach in order to improve search efficiency. For instance, [START_REF] Ford | Towards improving searches for optimal phylogenies[END_REF] describes a method splitting the set of characters into subsets for which the search for a perfect phylogeny is possible and then use the 'anchor' trees built on these subsets to constrain the search of the whole tree.

Drug Discovery

High throughput screening (HTS) refers to a set of techniques aiming at identifying biologically active molecules that exhibit useful properties among elements of a large database of chemical compounds. The selection of these candidate molecules together with an accurate prediction of their molecular activity is an important economic issue. In particular, such databases are used by the chemical industry and have a major value in pharmacology for developing new drugs and reduce the need for animal testing. They can contain millions of components. The key problem is to establish structure-activity relationships (SAR), i.e., to predict a biological activity from molecular descriptors and some knowledge on physico-chemical properties of chemicals. If we try to predict a degree of activity, we will talk about QSAR (quantitative SAR) and when activity is replaced by other physicochemical properties, we will talk about SPR (structure-property relationships). This question is at the crossroads of chemoinformatics and bioinformatics. Solutions are based on the assumption that "similar" molecules generally share a similar activity but it is far from being so simple in reality, some minor structural changes being enough to completely change the activity of a molecule. This problem is generally referred as the activity cliff [START_REF] Cruz-Monteagudo | Activity cliffs in drug discovery: Dr jekyll or mr hyde?[END_REF][START_REF] Dimova | Advances in activity cliff research[END_REF].

A fundamental notion in biochemistry is that of receptor/ligand interaction. A ligand is a substance that forms a complex with a biomolecule. Ligand binding to a receptor protein changes the 3D conformation and thus the functional state of this protein. When the structure of the target protein is known, the most commonly used approach is molecular docking (see Section 4) and the approach is called structurebased drug design (SBDD). There are now a number of drugs whose development was heavily influenced by SBDD, such as HIV protease inhibitors [START_REF] Kitchen | Docking and scoring in virtual screening for drug discovery: methods and applications[END_REF]. A recent review of work in this area is available in [START_REF] Ferreira | Molecular docking and structure-based drug design strategies[END_REF]. When the structure is unknown, the approach is called ligand-based drug design (LBDD) and the research described in the rest of this section mostly falls within this approach. In fact, most recent methods try to associate similarities of both ligands and receptor protein by concatenating their descriptors for learning classifiers. This computational chemogenomic approach is particularly useful for a casebased/analogical reasoning approach (see Chapter 10 of Volume 1), although it does not although it does not appear to have been formalized in these terms [START_REF] Brown | Compound Protein Interaction Prediction Within Chemogenomics: Theoretical Concepts, Practical Usage, and Future Directions[END_REF]. either when a target is searched for a new ligand on the basis of similarity with other ligands having known targets, or It applies either when searching for a new ligand on the basis of similarity with other ligands having known targets, or vice versa when searching for a new target on the basis of similarity with proteins having known active ligands.

Biological activity is generally dose-dependent and can be described by many parameters. In pharmacology, it is represented by two types of attributes, the activity of the target and the toxicity of the drug, which is itself described along four dimensions reflecting the life cycle of the substance and the different aspects of its transformation in the organism such as bio-availability or biodegradability (ADME: "absorption, distribution, metabolism, and excretion"). If all data and attributes can be turned into numerical or ordered values, it is possible to build mathematical functions that can predict the activities of new chemicals. Historically, the structureactivity study was based on simple models where the degree of activity was assumed to be a linear function of the measured properties (e.g. hydrophobicity) on chemical compounds. Simple statistical methods such as linear regression were typically applied for such studies. Since then, machine learning techniques have played an increasingly important role in this field [START_REF] Lavecchia | Machine-learning approaches in drug discovery: methods and applications[END_REF]. In its simplest form, the drug discovery challenge may be formalized as the following machine learning issue: Definition 4. Given a set of graphs labeled as positive or negative instances of molecular compound fragments with a given property, build a predictor for this property enabling the classification of new compounds.

The tested property can take various forms : activity (active/nonactive or a degree), drug-likeness, ADME property (absorption, solubility or permeability, metabolic stability, etc.), toxicity.

A number of open-source or commercial rule-based systems have been developed and are still used to solve this prediction problem in various domains such has skin sensitization, hepatotoxicity, or carcinogenic compounds [START_REF] Raies | In silico toxicology: computational methods for the prediction of chemical toxicity[END_REF]. Knowledge-based expert systems are routinely used to predict potential chemical toxicity, on the basis of qualitative evidence. For instance, Toxtree [START_REF] Benigni | Structure alerts for carcinogenicity, and the Salmonella assay system: A novel insight through the chemical relational databases technology[END_REF] operates with a a manually designed set of rules for evaluating the mutagenic/carcinogenic potential of chemicals. At a finer level, predicting xenobiotic metabolism (the way an organism degrades a chemical compound that it does not naturally produce in several metabolites) seems more challenging since a lot of false-positive can be produced [START_REF] Judson | Knowledge-Based Approaches for Predicting the Sites and Products of Metabolism[END_REF].

Besides expert systems, which assume the existence of a large knowledge base, there are of course automated prediction methods. The main methods in this field are Bayesian methods and SVM. The most recent ones use deep learning. Bayesian networks (see Chapter 8 of Volume 2) have been used in [START_REF] Abdo | Ligand-based virtual screening using bayesian networks[END_REF][START_REF] Abdo | Prediction of new bioactive molecules using a bayesian belief network[END_REF]. Authors propose to train a Bayesian belief network and use it in [START_REF] Abdo | Prediction of new bioactive molecules using a bayesian belief network[END_REF] to infer the activity class of a target compound. In the network, there is a terminal node for the target compound and other terminal nodes for sets of compounds known tho share some activity. The root nodes of the network represent the presence of specific fragments (substructures) in compounds. The calculation of conditional probabilities is adapted to the graph structure of chemical data and the target molecule is assigned to the most similar class based on the presence of common fragments. SVM (see Chapter 11 of Volume 1) have been used with Gaussian as well as simple linear kernels [START_REF] Hinselmann | Large-scale learning of structure-activity relationships using a linear support vector machine and problem-specific metrics[END_REF]. More specific kernels have been designed [START_REF] Vert | Machine learning for in silico virtual screening and chemical genomics: new strategies[END_REF], in particular graph-kernels that work on labeled graphs [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF]. Decision trees have also been used with some success, particularly Random Forests. For instance members of Pfizer showed that RF can produce results as good as SVM for predicting the relationship between the chemical structure of a compound and its metabolic stability [START_REF] Sakiyama | Predicting human liver microsomal stability with machine learning techniques[END_REF]. More recently, they have proved to be interesting for toxicology prediction (Tox21 challenge, [START_REF] Banerjee | Computational methods for prediction of in vitro effects of new chemical structures[END_REF]). RF have also been used for the protein-ligand docking problem in [START_REF] Ballester | A machine learning approach to predicting protein-ligand binding affinity with applications to molecular docking[END_REF]. molecules into the target's binding site (pose identification), and predicting how strongly the docked conformation binds to the target As for protein structure prediction (see section 4), deep learning has allowed to decrease the necessity to select optimal descriptors, although to the detriment of explainability of predictions. A good review of deep learning approaches in this field is available in [START_REF] Gawehn | Deep learning in drug discovery[END_REF]. Note that the search space is huge when crossing available chemical compounds and target proteins and the incompleteness of databases is a serious concern for all these methods [START_REF] Mestres | Data completeness-the Achilles heel of drug-target networks[END_REF]. For this reason, a number of authors stress the importance of active learning to better select the relevant part of databases or relevant experiments in order to transfer the available knowledge to new cases of protein-ligand association [START_REF] Wei | Submodularity in Data Subset Selection and Active Learning[END_REF][START_REF] Naik | Active machine learning-driven experimentation to determine compound effects on protein patterns[END_REF][START_REF] Reker | Multi-objective active machine learning rapidly improves structure-activity models and reveals new proteinprotein interaction inhibitors[END_REF][START_REF] Reker | Active learning for computational chemogenomics[END_REF]. In [START_REF] Reker | Active learning for computational chemogenomics[END_REF], authors use Random Forests for the learning component and propose a 'curiosity' criterion to select incrementally the relevant interactions in the database of known interactions. The curiosity measure selects each time the interaction for which there is the least consensus among the decision trees when classifying the interaction as active or not. This strategy, which is compatible with incremental selection of the most interesting experiments to refine the knowledge base, is also proving effective for machine learning using 10 to 20 percent of the database.

Except when drug discovery is based on deep learning techniques, the preprocessing phase is itself a hard problem, since it is necessary to extract from chemical databases the structural fragments that will be used as instances in the previous problem. This leads to a data mining problem: Definition 5. Given a set of graphs representing molecular compounds, build a set of frequently occurring subgraphs.

For a review of the multiple descriptors that have been used to represent molecular data, see [START_REF] Sawada | Benchmarking a wide range of chemical descriptors for drug-target interaction prediction using a chemogenomic approach[END_REF]. The structural and physicochemical fragments at the origin of the biological behavior of chemicals are often called structural alerts in the literature. One of the early AI approach for this problem is the system CASE (and later MultiCASE) [START_REF] Rannug | Use of artificial intelligence in structure-affinity correlations of 2,3,7,8-tetrachlorodibenzo-p-dioxin (TCDD) receptor ligands[END_REF], which considers structural subunits containing less than 10 connected heavy atoms and learns if they are active by measuring their occurrence probability with respect to a binomial distribution. Since then, the graph data mining approach has been prevalent [START_REF] Takigawa | Graph mining: procedure, application to drug discovery and recent advances[END_REF][START_REF] Sherhod | Emerging Pattern Mining To Aid Toxicological Knowledge Discovery[END_REF]. The search space of frequent subgraphs is explored either with a Breadth-First strategy (Apriori approach) or with a Depth-First strategy (Pattern-Growth approach). The AGM method [START_REF] Inokuchi | An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data[END_REF] uses the Apriori approach and works on canonical forms of graph adjacency matrices. It incrementally increases the size of matrices, merging at step k + 1 frequent matrices of size k resulting from step k. An interesting extension of this track of research proposes to integrate Apriori with the Version Space framework in order to produce the most specific and general molecular fragments corresponding to toxic compounds [START_REF] De Raedt | The Levelwise Version Space Algorithm and Its Application to Molecular Fragment Finding[END_REF][START_REF] Helma | The Molecular Feature Miner MOLFEA[END_REF]. This is in the full continuity of the founding work on the Meta-Dendral system that we mentioned in the introduction to this chapter Methods using the Pattern-Growth approach are described in [START_REF] Lepailleur | Automated detection of structural alerts (chemical fragments) in (eco)toxicology[END_REF]. From frequent atoms, they build increasingly larger frequent molecules by adding new bonds.The authors highlight the interest of searching for discriminating patterns (emerging patterns, jumping patterns) by considering frequency ratios (growth rate) in addition to frequencies, and especially most specific discriminating patterns (closed or representative pruned molecular patterns).

In [START_REF] Shao | Mining discriminative patterns from graph data with multiple labels and its application to quantitative structure-activity relationship (qsar) models[END_REF], the issue is set as mining discriminant subgraphs from graph data with multiple labels and it is shown how produced subgraphs can be applied to drug adverse effect prediction problem.

Among recent works, the notion of Pareto dominance with respect to a set of user-preference measures has proved to be of high importance for the selection of useful patterns (called skypatterns). The work described in [START_REF] Ugarte | Skypattern mining: From pattern condensed representations to dynamic constraint satisfaction problems[END_REF] proposes a static method whose efficiency is based on a condensed representation of patterns and a dynamic method whose effectiveness is based on improved pruning through iterative use of the patterns produced to refine dominance constraints. It is applied to the search of toxic chemical fragments, using as preference measures frequency, growth rate and chemical aromaticity. Authors have used the DynCSP framework of dynamical constraint solving [START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF] for posting new constraints from current sky patterns and the Gecode toolkit [START_REF] Schulte | Efficient Constraint Propagation Engines[END_REF] for the implementation.

Glycobiology

As for proteins, understanding the biological functions of carbohydrates (glycans) and relating them to their structure remains experimentally difficult and classification, machine learning or data mining methods are needed to propose general models or predictors of these functions. Unlike proteins, the information in databases [START_REF] Pérez | Glyco3d: a portal for structural glycosciences[END_REF][START_REF] Tiemeyer | GlyTouCan: an accessible glycan structure repository[END_REF][START_REF] Kanehisa | Kegg glycan. In A Practical Guide to Using Glycomics Databases[END_REF] are rooted trees with ordered children (up to 5) and not simply sequences, a characteristic that introduces interesting challenges. Moreover, the basic units of glycans (the nodes of the tree, monosaccharides) exist in numerous derived forms (e.g. more than 100 in bacteria). The root is a specific sugar that binds to its environment (cell or protein). The edges are made of several types of sugar bonds (say a dozen). The total number of glycans is estimated to be in the order of hundreds of thousands. This renders the representation of carbohydrates a difficult problem, more difficult than the analysis of trees that appear in RNA folding secondary structures.

Ontologies have started to be developed for this field. For instance, GlycoRDF [START_REF] Ranzinger | GlycoRDF: an ontology to standardize glycomics data in RDF[END_REF] proposes a standard OWL ontology that gives access for a number of glycomics databases to an RDF representation of various data ranging from publications relating to glycan structures to experimental datasets. Glycomics offers a nice setting to compare different technologies for graph databases or knowledge bases. For instance, RDF and Property Graph representation have been compared in respect of the glycan substructure search issue [START_REF] Alocci | Property graph vs rdf triple store:A comparison on glycan substructure search[END_REF], showing a clear advantage for RDF representations.

The physical recognition of glycan structures is currently treated by tandem mass spectrometry (MS/MS) and liquid chromatography. Two approaches are possible to infer a glycan structure from its MS/MS spectrum. In the simplest case we can use a large curated database of already known structures together with their spectra and develop a matching program for the annotation of a new spectrum. Sparql queries through RDF technology can be sufficient in this case. The other approach (de novo sequencing) tries to assign structures to peaks of the spectrum without any database. This requires machine learning methods to help peak assignment. The Glyfon program [START_REF] Kumozaki | A machine learning based approach to de novo sequencing of glycans from tandem mass spectrometry spectrum[END_REF] builds from a spectrum a graph of possible monosaccharide assignments and their links to other peaks using information on mass difference between two peaks and searches the space of all assignments compatible with a realistic glycan structure using an integer programming approach with Lagrangian relaxation. The parameters of the objective function are learned through a structured SVM, a task made tricky by the availability of a training set of structure-spectrum pairs, but not the corresponding residue-peak pairs. One of the main demands in glycomics bioinformatics tasks is the data mining of glycan structure databases to classify glycans and discriminate the classes on the basis of the structural patterns that they contain [START_REF] Mamitsuka | Glycoinformatics: Data Mining-basedApproaches[END_REF]. Genetic programming has been adapted in [START_REF] Miyahara | Learning of glycan motifs using genetic programming and various fitness functions[END_REF] to learn glycan motifs through the use of tag tree patterns. An interesting adaptation of SVM classifiers has been proposed in [START_REF] Yamanishi | Glycan classification with tree kernels[END_REF], who introduce tree kernels for glycans. In practice, a tree kernel measures the similarity between two trees by counting the number of common subtrees, possibly with the same size and/or the same depth, and a powerful restriction is to consider only subtrees that are close with respect to the sibling relation (co-rooted trees).

Since motifs are as important as the identification of classes, the choice of features has to be compatible with a feature selection method in order to extract the high-scoring subtrees. Authors have applied this work with success to the task of predicting the blood origin of glycans among leukemic and non-leukemic blood cell types and finding a glycan motif typical of leukemic cells. Instead of using a dedicated kernel and then extracting features, some authors have tried to directly produce the relevant attributes through pattern mining in glycan structures, the presence of each frequent subtree becoming a binary attribute. A method is proposed in [START_REF] Takigawa | Mining patterns from glycan structures[END_REF], which claims better results on a mixed set of existing and randomly synthesized glycans than the previous method.

Frequent subtrees are extracted using two criteria, the search of subtrees that are significantly more frequent than the tree they come from and the search of significant subtrees with respect to a Fisher test using a control dataset.

A more ambitious approach for analyzing the structure of glycans is to use formal grammars. This way, one can not only discover motifs (associated to non-terminals of the grammar) but also the hierarchical relations they share (the rules of the grammar). T. Akutsu has introduced elementary ordered tree grammars for this purpose [START_REF] Akutsu | A bisection algorithm for grammar-based compression of ordered trees[END_REF], where production rules use trees with edges labeled either using terminal or non-terminal symbols and one leaf in the tree may be tagged to indicate where another tree may be attached. Grammars are restricted to Chomsky's normal form (two non-terminals on the right-hand side). The idea is then to use grammarbased compression as a criterion to find interesting structures: the problem is to find the smallest grammar that generates exactly a given tree. An integer programming model is proposed in [START_REF] Zhao | Integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures[END_REF], with a small experimentation on glycan trees labeled with the types of monosaccharides and the use of Cplex as a solver. This work is extended in [START_REF] Zhao | Grammarbased compression approach to extraction of common rules among multiple trees of glycans and rnas[END_REF] to take into account multiple trees, this time using glycans labeled with the glycosyl transferases that enable the linkage of monosaccharides in the construct (a small experiment on RNA secondary structures is also provided). An interesting point in this extension is that a grammar could directly reflect the construction process of the molecule.

In this respect, glycobiology offers a specific application field for pathway reconstruction techniques (see 5). Indeed, the formation of each glycan structure results from dedicated biochemical pathways using polymerization reactions catalyzed by specific enzymes. One important question is thus to associate one or several genes corresponding to these enzymes to reactions that progressively transform a glycan structure. This can be studied in bacteria thanks to knockout experiments observing the effect of discarding a gene on the produced structures and the presence/absence of genes in related strains, as it is used in [START_REF] Sternberg | Gene function hypotheses for the campylobacter jejuni glycome generated by a logic-basedApproach[END_REF]. This paper demonstrates the application of inductive logic programming (Progol) to learn the generule associations. Authors emphasize the interesting fact that aside from using some background knowledge on biochemistry (pathways, decomposition of glycan) and strain serotypes, it is necessary to introduce some speculative assumptions to better score the competing hypotheses. As in other areas of Artificial intelligence, it appears that the formalization of preferences has been key to successful predictions.

It seems that there is still scope for other research on this problem, using other techniques, and to our knowledge, no grammatical inference method has been applied so far to look at a grammar generalizing a positive training set of glycan structures and possibly rejecting a negative training set. The last study also points to the interest in the development of preference reasoning and possibly preference learning to help select from the predictions a reasonable subset of hypotheses that will be the subject of experimental testing.

There are also probabilistic approaches that have proposed extensions of Hidden Markov Models for the treatment of ordered trees. Among the most interesting ones, Ordered Tree Markov Model (OTMM) considers dependencies between parents and their first child and dependencies between ordered children [START_REF] Ueda | A probabilistic model for mining labeled ordered trees: capturing patterns in carbohydrate sugar chains[END_REF], and profilePTSMM (Probabilistic Sibling-dependent Tree Markov Model) considers two different types of transition dependencies between parents and all their children and dependencies between ordered children, together with the introduction of match/delete and insert states as in profile HMM [START_REF] Aoki-Kinoshita | Pro-filePSTMM: capturing tree-structure motifs in carbohydrate sugar chains[END_REF][START_REF] Aoki-Kinoshita | Analyzing Glycan-Binding Patterns with the ProfileP-STMM Tool[END_REF].

Another common task in glycomics is the prediction of the glycosylation state of proteins. There are four types of glycosylation, the main one being O-linked and Nlinked glycosylation, then C-linked glycosylation. It is known to occur on particular sites in the protein, partially characterized by short sequence motifs. The issue is to predict the glycosylation type and the sites.

The glycosylation site prediction problem

• Given a type of glycosylation, given a set P of proteins with known sequence and glycosylation sites and some optional background knowledge providing functional features or annotations for any protein,

• Build a classifier that can predict the glycosylation sites of this type in a new protein.

Of course, it is possible to state the problem as a three-or four-class problem instead of building one classifier for each type.

As in many bioinformatics applications, the difficulty is to find a trade-off between the number of parameters of the learned models and the relative scarcity of available data. Several predictors are often combined to this end.

For example, in [START_REF] Senger | Prediction of n-linked glycan branching patterns using artificial neural networks[END_REF] a set of recurrent Elman networks are trained to predict the major presence of a certain type of glycans in N-linked glycosylation of proteins, the training data being provided by predictors of the secondary structure and the accessibility state of these proteins from their sequence. In [START_REF] Chauhan | In silico Platform for Prediction of N-, O-and C-Glycosites in Eukaryotic Protein Sequences[END_REF], using the same type of information, the three major types of glycosylation are predicted with an SVM-based approach, using a Gaussian RBF kernel and a carefully selected non-redundant dataset. Authors have chosen this approach after testing numerous methods available in the Weka machine learning toolkit (namely Random Forest, Logistic Model Trees, various types of SVM in libsvm and with Sequential Minimal Optimization SMO, Bayesian network and naive Bayes). The philosophy of the best methods is to use a maximum number of attributes, including derived attributes that result from auxiliary predictors, and to add a feature selection stage to avoid overfitting. Among state-of-the-art methods at the time of this review, GlycoMine [START_REF] Li | Glycomine: a machine learning-based approach for predicting n-, c-and o-linked glycosylation in the human proteome[END_REF] makes use of a knowledge base extracted from a number of databases of protein features (Gene ontology, Kegg, Pfam, Uniprot, etc.) and uses a feature selection procedure based both on mutual information and information gain.

It is likely that many problems studied on sequences will have an extension on glycan trees. It is thus a new field of study and application of AI techniques developed for sequences to these more complex structures. For instance, algorithms have been developed recently for glycan multiple alignments [START_REF] Hosoda | Development and application of an algorithm to compute weighted multiple glycan alignments[END_REF] and it would be interesting to check ideas developed on sequence multiple alignment (see section 6) in this new context.

Conclusion

Bioinformatics is a field full of incomplete data, knowledge expertise and NPcomplete problems, and is as such a playground offering many opportunities for Artificial intelligence studies. This exciting interdisciplinary field comes at a cost. The first difficulty is to cope with the rapidly advancing technology. It is not always easy to distinguish short term problems that will be rapidly obsolete thanks to the next generation technology from more fundamental issues that are created by accessing a new kind of data. Two significant trends seem, however, to be emerging in this field.

First, there is an extensive use of weighted sequence data to cover all omics observations, giving both access to their qualitative and quantitative content. A weight may be a quality score that reflects the probability that a letter at a given position in the sequence was correctly observed by the sequencer (this tends to be standardized in file formats like FastQ, which codes letters as well as quality by ASCII characters) or an abundance (read count) that reflects the degree of expression of an element of the sequence in the observed sample. Sequencing is no longer reduced to the analysis of DNA and is now applied as a high-throughput technology for the identification of chromosomal 3D structures, the observation of epigenetic factors like DNA methylation or histone modification, the analysis of coding and non-coding types of RNA, translation efficiency of proteins [START_REF] Mglincy | Transcriptome-wide measurement of translation by ribosome profiling[END_REF], and all the interactions like the interactions between DNA and proteins [START_REF] Soon | High-throughput sequencing for biology and medicine[END_REF]. This unification from the technological side is good news for all researchers in Bioinformatics since it provides some stability to their results.

Secondly, access to individual observations, which started with genomes of individual organisms and culminates now in the development of single cell analysis [START_REF] Baron | New skin for the old rna-seq ceremony: the age of single-cell multi-omics[END_REF][START_REF] Bock | Multi-Omics of Single Cells: Strategies and Applications[END_REF][START_REF] Gawad | Single-cell genome sequencing: current state of the science[END_REF][START_REF] Yuan | Challenges and emerging directions in single-cell analysis[END_REF], is a clear breakthrough in molecular biology. Understanding the pool of variations that lead to diseases, analyzing a microbial community and the exchanges that occur between its elements and tracking the embryonic development of a pool of cells, are all attainable with the technological developments. It opens the door to personalized medicine and to the rational representation and understanding of populations at all levels. Most likely, new types of intelligent models and methods are needed and will emerge to address these new challenges.

Once the raw data have been preprocessed, what makes studies successful is a deep understanding of the peculiarities of a particular biological question. The devil is in the detail. These peculiarities are key to addressing the complexity and push forward the boundaries of feasibility, but it is also a guarantee that relevant solutions for the biologist will be proposed. Of course, it is possible to work with standard benchmarks and build on the accomplishments of predecessors. But there are plenty of opportunities to participate in biological discoveries. The only advice I could address to AI people eager to start out in this field and contribute to these discoveries is to keep their focus on a specific set of questions and to ensure that there is a biologist expert on these questions in the loop.

Besides standard biology, an alternative and much more prospective route to cooperation between computer science and biology is synthetic biology, a field interested by life engineering, trying to design living components with simplified, fully controlled behaviors that can be assembled. It is not only a question of introducing a new technology: since experiments can be better controlled, it provides key to an indepth understanding of living systems. This could be inspiring for AI in its goal of better understanding the components of intelligence. Neurons are no more the sole interesting cells in this respect. It has been shown by T. Nakagaki for instant that even primitive systems like ciliates or slime are able to memorize and have learning capacities. Some authors start to think of BI (Bio-artificial Intelligence) after AI [START_REF] Nesbeth | Synthetic biology routes to bio-artificial intelligence[END_REF]] by looking at ways to implement learners with synthetic gene and protein networks.

Acknowledgements I would like to thank authors of the French version of this chapter who offered me a primary material of quality to start this English version: F. Coste, C. Nédellec, T. Schiex and J.P. Vert. Thanks also to O. Dameron and F. Coste for their proofreading of the manuscript.