Global Optimization for Scaffolding and Completing Genome Assemblies

Sebastien François 1 Rumen Andonov 1 Dominique Lavenier 1 Hristo Djidjev 2
1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA_D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Résumé : Ce travail porte particulièrement sur les étapes de scaffolding et de gap-filling lors de l’assemblage de novo d’un génome. Etant donné un ensemble de contigs et leurs relations (chevauchement et/ou éloignement), nous proposons une approche basée sur l’optimisation, qui consiste à trouver le plus long assemblage possible consistant avec les distances attendues. Nous résolvons ce problème en le formulant sous la forme d’une programme mixte en nombres entiers (MILP). Notre méthode permet de résoudre exactement des instances comptant jusqu’à 6682 variables binaires pour 165 contigs. L’un des avantages de notre modélisation est qu’elle permet de résoudre simultanément différentes sous taches spécifiques à l’assemblage complet d’un génome : déterminer l’orientation de chaque contig, ordonnancer les répétitions, compléter les scaffolds et les étendre en un assemblage unique etc. . . Ce qui constitue d’ordinaire un ensemble de problèmes à traiter séquentiellement. (Nécessitant alors des solutions spécifiques pour chacun d’entre eux). A notre connaissance, aucune autre approche ne propose de réduire le problème de l’assemblage génomique à celui de la recherche du plus long chemin.
Type de document :
Communication dans un congrès
International Network Optimization Conference , Feb 2017, Lisboa, Portugal. pp.15, 2017, 〈http://inoc2017.fc.ul.pt/〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01499859
Contributeur : Rumen Andonov <>
Soumis le : samedi 1 avril 2017 - 08:31:29
Dernière modification le : jeudi 11 janvier 2018 - 06:28:15
Document(s) archivé(s) le : dimanche 2 juillet 2017 - 12:34:54

Fichier

RR-9050 (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01499859, version 1

Collections

Relations

Citation

Sebastien François, Rumen Andonov, Dominique Lavenier, Hristo Djidjev. Global Optimization for Scaffolding and Completing Genome Assemblies. International Network Optimization Conference , Feb 2017, Lisboa, Portugal. pp.15, 2017, 〈http://inoc2017.fc.ul.pt/〉. 〈hal-01499859〉

Partager

Métriques

Consultations de la notice

282

Téléchargements de fichiers

76