Preface

Scientists have long been interested in studying living organisms, both at a macroscopic scale, by analyzing their external appearance or their overall internal functioning, and at a more microscopic scale. Taken to its extreme, their observation consists of studying the nucleus of cells and the molecules of living organisms that define their functioning: namely DNA and RNA. In an organism, DNA is actually the carrier of genetic information, which is called the genome, thus playing an important role. However, the genome is not everything; it is composed of genes that allow for RNA production which have various functions such as protein synthesis or regulation of cell activity. In digital form, these DNA or RNA molecules are most often represented as text from four-letter alphabets (A, C, G and T for DNA; A, C, G and U for RNA). Using these DNA and RNA sequences, computer-based methods are able to answer a number of biological questions. This is the heart of this book. In the chapters of this book, we will find the answers to these questions, as well as their limitations to some fundamental questions that have been, and are still being, addressed by bioinformatics. How can a short sequence of a few hundred nucleotides quickly be searched for in a genome that can make a few billion of them? How can sequences be compared with one another? How can the complete sequence of a genome be reconstructed? How can the bacteria that make up our intestinal flora be identified? Based on their sequences, how can the structure that certain RNAs will adopt be predicted?

The methods that are described in this book have their roots anchored in two fields with long-standing foundations, which have long evolved alongside each other without any significant interaction: computer science and biology. It was during the 20th century that the symbiosis between computational methods and biological problems led to combined modeling and the design of bioinformatics algorithms, methods and tools.

DNA was first sequenced in the late 1970s, with low volumes and incurring huge costs. The need to store and manipulate this data automatically soon became very pressing. As a result, the mid-1980s witnessed the development of the first sequence databases. These databases are pooled by the community who feeds them sequencing experiments, which are increasingly growing and require more efficient methods. This is how sequence alignment methods are implemented, which are dedicated to these genomic sequences, and designed for optimizing the time and space used for this operation. These databases are not only maintained, but also expanded and made public internationally, further accelerating access to knowledge. Data acquisition is also accelerating since the first complete bacterial or yeast genomes in the mid-1990s, as well as with the human genome project, which has kept many teams busy for over a decade. Access to knowledge about these genomes leads to questioning living organisms from a completely new point of view, and opens up new avenues for several fields of application, particularly in the health sector, and also in ecology and evolution, along with the enrichment of the fundamental knowledge of organisms and how they function.

Since the mid-2000s, genomic data have been acquired at a much faster pace following the advent of high-throughput sequencers, which enable, to a certain extent, the transformation of DNA or RNA molecules into short sequences of letters at a low cost and at an increasingly frenetic pace. There is an ongoing discussion of projects involving several thousand, or even tens of thousands, complete genomes of individuals of interest. These developments make it now possible to question living organisms in a finer manner, at the scale of varieties and individuals of the same species, but also at the scale of the different tissues that make up an organism, or even at the scale of a natural environment sample containing thousands of different organisms. With these new questions emerges the need to model data as a whole, in a structured way, and to develop methods for the purpose of answering them.

At the same time, storage and information processing capacities, as well as computational performance allowed by increasingly powerful processors and exploiting increasingly complex parallelism, have accompanied an extraordinarily rapid progress in the field of algorithmics and problem modeling based on the use of elaborate discrete structures. Some particular operations that seemed inaccessible have become commonplace at a lower cost in modern programs, and it is not uncommon today to run calculations over a grid whose capacities far exceed what could be imagined some 20 years ago. Nonetheless, this is not enough to make feasible all the studies that we would like to achieve on sequencing data and their derivatives.

The data produced by the sequencers, due to their quantity (up to 10 million nucleotides per second) and their particularities (whose lengths and types of errors vary according to sequencing technologies), require the appropriate use of methods in order to extract relevant information therefrom in a reasonable amount of time without resorting to gigantic computing infrastructures.

Although the methods developed are generally independent of the technology, they must take into account the constraints of the technology in order to yield solutions for practical applications. In particular, the increase in the volume of data to be processed makes some solutions impractical and requires the use of much more faster heuristics. Therefore, the methods used in bioinformatics are most often at the crossroads between exact and approximate methods.

In order to better understand the specific terms and tools of bioinformatics, we have introduced most of them in Chapter 1. This chapter also covers in detail the data (DNA, RNA and proteins) which we are working with, and the way they are obtained. Moreover, this chapter presents some algorithmic notions that are useful for understanding this book, and addresses the concepts used in bioinformatics more broadly. The remaining chapters present the most commonly studied problems in bioinformatics from genomic data. Some chapters focus more on tools, others on methods and still others on a more detailed description of data. We briefly present the questions which the following chapters of this book will answer.

Sequence indexing. In order to address the influx of data, how can these be easily stored, queried and manipulated? This is the subject of Chapter 2, which explains how to respond to these different aspects. The crucial issues here are the conservation of information, the flexibility of the structure and its ability to answer in a reasonable time the most common question, namely "Is this sequence indeed in my genome?"

Sequence alignment. When studying one or more sequences, a question arises very quickly: how can we tell whether the sequences are similar if a sequence is approximately found in another, and also can a score that allows for classifying these comparisons between them be determined? A crucial point in bioinformatics is to be able to answer the question "What are the most significant occurrences of my pattern in my sequence?" This is what is called the sequence alignment, which is the subject of Chapter 3. This chapter also deals with the aspects of alignment-free comparison where, in order to cope with the volume of data and sometimes significant error rates, making use of an alignment is not feasible and heuristics are developed.

Genome assembly. In Chapter 4, the following question is addressed: "How can the complete sequence of an organism be obtained based on the reads produced by sequencing?" This fundamental problem thus arose from a technical difficulty that makes it impossible to read the genome of an organism in one piece from its cells. This technical difficulty will most likely disappear if advances in sequencing make it possible to read the genome in a single pass; however, the assembly is for the moment essential to the knowledge of the genome and raises many problems, such as "how to choose between two possibilities to assemble the reads?" or "how could the quality of the reconstruction be evaluated?" Graphs prove to be very interesting models in this context of reconstruction.

Metagenomics and metatranscriptomics. When several organisms are mixed in a sample, for example, of soil, from a marine environment or from the internal environment of an organism (the well-known microbiota), additional problems can occur along with those already existing during the assembly. For example, "how can we determine which species are present?" or still "how can genomes be assembled when they are mixed together?" This is the subject of Chapter 5.

RNA folding. RNA data are particular data because their secondary structure plays a fundamental role in the functioning of organisms. Chapter 6 proposes an overview of methods for modeling and inferring this secondary structure from sequence data. Here the fundamental question is "how can the folding of a word on itself be found and evaluated, taking into account the affinities between the characters of this word?"

Apart from the solutions provided to answer this large number of questions, it now becomes all the more necessary to take a step back from the methods capable of processing these data. What does it mean when we "find the same piece of sequence" of one organism in another, and what is the significance of...