Assemblage (bio-informatique)

En bio-informatique, l'assemblage consiste à aligner et/ou fusionner des fragments d'ADN ou d'ARN issus d'une plus longue séquence afin de reconstruire la séquence originale. Il s'agit d'une étape d'analyse in silico qui succède au séquençage de l'ADN ou de l'ARN d'un organisme unique, d'une colonie de clones (bactériens par exemple), ou encore d'un mélange complexe d'organismes. Le problème de l'assemblage peut être comparé à celui de la reconstruction du texte d'un livre à partir de plusieurs copies de celui-ci, préalablement déchiquetées en petits morceaux. Les stratégies d'assemblage peuvent être organisées en 3 principaux paradigmes. Historiquement la première stratégie d'assemblage, celle-ci consiste à faire systématiquement le meilleur choix disponible sans possibilité de revenir sur ce choix plus tard. Le principal défaut de cette stratégie est qu'elle mène à des optimums locaux sans prendre en compte la relation globale entre les fragments. La plupart des assembleurs gloutons utilisent des heuristiques pour éviter le mauvais assemblage de séquences répétées. La plupart des premiers assembleurs tels que Phrap ou TIGR reposent sur ce paradigme, ainsi que quelques outils plus récents comme VCAKE. Cette stratégie d'assemblage se déroule en 3 étapes: Construction d'un graphe d'intervalles de chevauchement de fragments. Chaque fragment est un nœud du graphe, et une arête est créée entre deux fragments lorsque ceux-ci se chevauchent. Simplification du graphe. Des sous-graphes denses sont identifiés comme une collection de fragment qui se chevauchent entre eux et qui proviennent probablement de la même séquence originale. Extraction des séquences consensus. Une séquence consensus (contig) est générée à partir de l'ensemble des fragments de chaque sous-graphe. Une variante de cette stratégie consiste à supprimer les liens transitifs du graphe de chevauchement pour construire un string graph. Ce paradigme a notamment été rendu populaire par les travaux de Gene Myers intégrés dans l'assembleur Celera.