Integer Programming Approach for Nested Pairs Genome Scaffolding
| Autor: | Epain, Victor, Andonov, Rumen |
|---|---|
| Přispěvatelé: | Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT) |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Contig
Elementary longest path problem [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Integer programming [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] Scaffolding Quantitative Biology::Genomics NP-Hard problem De novo genome assembly |
| Popis: | Scaffolding step in the genome assembly aims to determine the order and the orientation of a huge number of previously assembled genomic fractions (contigs/scaffolds). Here we introduce a particular case of this problem and denote it by Nested Pairs Scaffolding. We formulate it as an optimisation problem and propose an integer programming formulation for its resolution. The performed computational results on real and synthetic data show an excellent behaviour of our formulation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|