Recherche opérationnelle – Optimisation combinatoire

14h30
IRCAM - Salle Stravinsky
1, place I. Stravinsky 75004 Paris
Entrée libre

Avec la participation de Christoph Dürr (LIP6, CNRS/Université Pierre et Marie Curie), Philippe Esling (Department of Genetics and Evolution, Université de Genève, Suisse), Daniel Schell et Ola Rinta-Koski.

Programme [PDF]

• 14h30-15h15 : Daniel Schell, Ola Rinta-Koski et Thomas Pintelon
  La connexion optimale d’accords
• 15h30-16h15 : Christoph Dürr
  Ordonnancer le plus froid d'abord pour approximer le débit
• 16h30-17h15 : Philippe Esling
  Quantifying the unknown: Metagenomics analysis of deep-sea ancient DNA

Une connexion entre accords est optimale si la somme des intervalles dans enchainements de voix est réduite à un minimum. La théorie de base de l’harmonie décrit comment connecter les accords avec de petits intervalles, note sensible, lignes en demis tons et, si possible, notes tenues. Ces règles sont particulièrement en usage dans la composition du choral.

Les pianistes, particulièrement les improvisateurs, savent comment minimiser les déplacements de leurs doigts lorsqu’ils se déplacent d’un accord à l’autre. Ceci pourrait être formulé comme une recherche de distances minimales. De la même façon, nous pouvons considérer que, à certains moments du choral, nous désirons minimiser les intervalles dans la conduite des voix. Si nous acceptons que l’énergie dépensée par un chanteur, lors d’un saut de voix, est proportionnelle à la longueur de l’intervalle, alors la connexion optimale d’accords devient équivalente à un problème de minimisation de ressources sous contraintes.

Les compositeurs ont l’habitude de connecter des 3-accords et des 4-accords (triades ou tétrades) dans le système tempéré à 12 tons, dit Z12. Nous avons trouvé intéressant de généraliser cette procédure à des accords de toutes tailles, des p-accords, sur un système de division à n intervalles, Zn. Ceci est donc une tentative de généraliser les formules de l’harmonie traditionnelle. Considérant qu’une formule de progression d’accords connectés comme I7-IIm7-V7-I7 est d’usage courant sur Z12, nous nous demandons pourquoi, et nous tentons de savoir si des formules analogues peuvent être trouvées entre accords de différentes tailles p, sur différents Zn.

Dans notre étude, le procédé de connexion d’accords est comme suit :

1. Connexion d’accords de même taille, par paires.
2. Trouver le chemin le plus court entre les séquences d’accords connectés par paires.

Pour connecter les accords par paires, nous utilisons et comparons trois différentes méthodes : (i) L’énumération exhaustive; (ii) La recherche par assignation dans les matrices de transition (l’algorithme Hongrois); (iii) La recherche en graphe, règle profondeur d’abord.

Pour la recherche du chemin le plus court entre sequence d’accords nous utilisons des algorithmes du type Voyageur de Commerce. Pour de petits accords et sur des systèmes Zn de divisions de petites tailles, l’énumération exhaustive (i) et les deux méthodes de recherche (ii) et (iii) ont été utilisées. Leurs résultats ont été comparés, ce qui nous a permis de vérifier les algorithmes. Ces derniers ont ensuite été utilisés pour des systèmes de p-accords et de divisions Zn de plus grande taille, là où l’énumération exhaustive n’est plus possible.

Pour ce séminaire MaMuX j'ai choisi de parler d'un travail qui exhibe un lien entre le comportement d'un algorithme d'ordonnancement et la discrétisation d'une droite de pente rationnelle. Le modèle est le suivant. Nous disposons d'un ensemble de tâches de taille unitaire à exécuter sur un processeur. Chaque tâche a une contribution de température h donnée. Si la température du processeur est t et qu'il exécute cette tâche, elle est (t+h)/2 après l'exécution. Si le processeur ne fait rien par contre la température chute à t/2. La température du processeur ne dois jamais dépasser la valeur 1 (normalisé). Le but est d'ordonnancer un plus grand nombre de tâches avant une date limite commune D. Ce problème est NP-complet. Dans ce travail nous analysons le rapport d'approximation d'une politique d'ordonnancement très simple, qui exécute à tout moment la tâche de la plus petite contribution de température, si c'est possible.

Ce travail est en commun avec Ioannis Milis, Julien Robert and Georgios Zois.

The estimation of biological diversity is an uprising research topic in genetic analysis. The goal of metagenomics is to analyze the complex micro-organism communities that can be found from the bottom of the deep-sea to the very inside of our own bodies. The estimation of eukarotic richness and diversity in the environment has became available through the advent of next-generation DNA sequencing (NGS) for metagenetics. A new approach, called "barcoding" showed that we can accurately identify and distinguish species through very small fragments of their DNA. These hypervariable regions can be targeted by using specific primers, that allow to amplify these Small Sub-Units (SSU), usually through the 16S or 18S rRNA gene.

The recent advances in NGS technology offer an unprecedent throughput and coverage of genetic material. However, the amount of data generated by such platforms consequently raises algorithmic issues due to the average billion-sized sequence datasets. After several years of research in metagenomics, we are starting to uncover the tip of an unprecendent picture on the eukaryotic diversity. However, this explosion of research came with a plethora of approaches, variety of methodologies and heterogeneity on the concept of species. This current deluge of data have hindered the possibility of obtaining an authoritative view on biological diversity evaluation. The first studies in this research field revealed an incredible diversity that could range over thousands of different microbial species living in our bodies. However, not only the size and depth of sequencing can provoke an over-estimation of diversity, but a plentiful of biases hinders the results all along the way of genetic analysis

1. In-vivo biases: Intra-genomic variations and extra-cellular DNA (eDNA) survival
2. In-vitro biases: Laboratory contaminations, PCR-Related biases, chimeras, primers dimers
3. In-silico biases: Reads quality, Sequencing errors, Primers mismatches
4. Biochemical transformation of nucleotides: Because we are currently analyzing ancient DNA that can be tens of thousands years old, the nucleotides can undergo chemical properties changes that transform one base into another.

We delineate these biases and their effects on genetic sequence analyses. First, we show our advances in devising an ultra-fast diversity estimation pipeline and show the superiority of our approach. We then present the implications of our results on the biological interpretation of diversity. A recent ultra-deep sequencing of the Sea of Japan revealed that most of the diversity found in DNA analyses was in fact biased by eDNA. This indicates that strands of DNA from dead species would regroup in the deep-sea and can pertain for very long periods of time. This stress out the importance of developing rRNA sequencing which implies harder and much more tedious laboratory protocols.

Finally, we open the debate upon the epistemological differences between exploratory and hypothesis-driven research in this field. We raise the question of how to quantify the unknown and find new species without having any prior knowledge on their underlying sequences. The worst thing not to know is what is not known to be unknown.