Recanati, Antoine
[Author]
;
Paris Sciences et Lettres (ComUE)
[Contributor];
Aspremont, Alexandre d'
[Contributor]
Relaxations of the seriation problem and applications to de novo genome assembly ; Relaxations du problème de sériation et applications à l’assemblage de génome de novo
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Electronic Thesis;
E-Book
Title:
Relaxations of the seriation problem and applications to de novo genome assembly ; Relaxations du problème de sériation et applications à l’assemblage de génome de novo
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Les technologies de séquençage d’ADN ne permettent de lire que de courts fragments, dont on ignore la position sur le génome. L’assemblage de novo vise à reconstituer une séquence d’ADN entière en mettant ces fragments bout-à-bout, tel un puzzle. Dans l’approche OLC (overlap-layout-consensus), on calcule le chevauchement entre fragments afin de les disposer en ordre (réarrangement), puis extraire une séquence consensus. Le réarrangement peut s’écrire comme un problème combinatoire de sériation, où l’on réordonne des éléments comparables entre eux, de sorte que deux éléments adjacents sont similaires. Ce problème est résolu efficacement par un algorithme spectral en l’absence de bruit, mais il en va autrement des données génomiques réelles. En particulier, des régions du génome sont similaires bien qu’éloignées (séquences répétées), rendant l’assemblage problématique. Les méthodes d’assemblage emploient des algorithmes hiérarchiques et gloutons pour désambiguïser les séquences répétées. Nous proposons ici une approche épurée où l’on réarrange tous les fragments « d’un coup »via la résolution de sériation. Notre première contribution montre que l’emploi de la méthode spectrale pour le réarrangement s’intègre par- faitement dans le schéma OLC, produisant des résultats de qualité semblable aux méthodes standard. Ce- pendant, du fait des séquences répétées, cette méthode produit des assemblages fragmentés (typiquement en quelques sous-séquences au lieu d’une). La deuxième contribution est un prolongement de la méthode spectrale lié à la réduction de dimension sous conservation de distances, englobant les problèmes de sériation et de sériation circulaire (une variante où les éléments peuvent être ordonnés selon un cycle) dans un cadre unifié. Ce prolongement rend l’algorithme robuste au bruit et résout le problème de fragmentation de l’assemblage précédent. Notre troisième contribution formalise la sériation robuste, où l’on souhaite réordonner des données bruitées. Nous décrivons des liens avec d’autres problèmes ...