New Polynomial-Time Algorithm around the Scaffolding Problem

We describe in this paper an approximation algorithm for the scaffolding problem, which is part of genome inference in bioinformatics. The aim of the problem is to find a maximum weighted collection of disjoint alternating cycles and paths covering a particular graph called scaffold graph. The problem is known to be NP-complete, and we describe further result concerning a special class of graphs aiming to be close to real instances. The described algorithm is the first polynomial-time approximation algorithm designed for this problem on non-complete graphs.

Domaines

Bio-informatique [q-bio.QM] Complexité [cs.CC]

Fichier principal

main.pdf (512.52 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Tom Davot : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02047701

Soumis le : lundi 25 février 2019-10:52:33

Dernière modification le : samedi 27 avril 2024-03:16:39

Archivage à long terme le : dimanche 26 mai 2019-13:16:19

Dates et versions

lirmm-02047701 , version 1 (25-02-2019)

Identifiants

HAL Id : lirmm-02047701 , version 1
DOI : 10.1007/978-3-030-18174-1_2

Citer

Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. New Polynomial-Time Algorithm around the Scaffolding Problem. AlCoB 2019 - 6th International Conference on Algorithms for Computational Biology, May 2019, Berkeley, United States. pp.25-38, ⟨10.1007/978-3-030-18174-1_2⟩. ⟨lirmm-02047701⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

ENPC CNRS INSMI PARISTECH LIGM LIGM_MOA MAB MAORE LIRMM MIPS UNIV-MONTPELLIER UNIV-EIFFEL LIGM_ADA JSE2024

143 Consultations

195 Téléchargements