HAL TEI export of lirmm-02047701 CCSD CC0 1.0 - Universal

HAL API Platform

 New Polynomial-Time Algorithm around the Scaffolding Problem Tom Davot 5008d5f43f4a2c57835866c34db633fa lirmm.fr 1180468 2202171-1180468 https://orcid.org/0000-0003-4203-5140 Annie Chateau 4c0e4613d8ee10ee4e1c98180000b379 lirmm.fr annie-chateau 173624 44100-173624 https://orcid.org/0000-0003-4760-8171 https://www.idref.fr/227798856 Rodolphe Giroudeau 3eafab1248c9498dcf1c870a3b621a56 lirmm.fr rodolphe-giroudeau 172373 17662-172373 https://www.idref.fr/095605355 Mathias Weller d4090dfdea08661d21a4a05d289d7c6b u-pem.fr mathias-weller 16443 27406-16443 https://orcid.org/0000-0002-9653-3690 https://arxiv.org/a/weller_m_1 bsdr7SwAAAAJ Tom Davot 5dd6bc4f166bfa1ded97930455793169 univ-angers.fr 2019-02-25 10:52:33 2026-04-02 11:58:01 2019-03-04 19:36:21 2019-05-28 2019-02-25 contributor Tom Davot 5dd6bc4f166bfa1ded97930455793169 univ-angers.fr CCSD lirmm-02047701 https://hal-lirmm.ccsd.cnrs.fr/lirmm-02047701 davot:lirmm-02047701 <i>AlCoB 2019 - 6th International Conference on Algorithms for Computational Biology</i>, May 2019, Berkeley, United States. pp.25-38, <a target="_blank" href="https://dx.doi.org/10.1007/978-3-030-18174-1_2">&#x27E8;10.1007/978-3-030-18174-1_2&#x27E9;</a> AlCoB 2019 - 6th International Conference on Algorithms for Computational Biology, May 2019, Berkeley, United States. pp.25-38, &#x27E8;10.1007/978-3-030-18174-1_2&#x27E9; HAL Authorization École nationale des ponts et chaussées CNRS - Centre national de la recherche scientifique CNRS-INSMI - INstitut des Sciences Mathématiques et de leurs Interactions ParisTech Laboratoire d'informatique Gaspard-Monge Models and Algorithms Méthodes et Algorithmes pour la Bioinformatique Méthodes Algorithmes pour l'Ordonnancement et les Réseaux Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier Mathématiques, Informatique, Physique et Systèmes Université de Montpellier Université Gustave Eiffel Université Paris-Est Marne-la-Vallée ESIEE Paris Université de Montpellier (2015-2021) TEST3-HALCNRS Algorithmique Discrète et Applications International No No Yes Yes New Polynomial-Time Algorithm around the Scaffolding Problem Tom Davot 5008d5f43f4a2c57835866c34db633fa lirmm.fr 1180468 2202171-1180468 https://orcid.org/0000-0003-4203-5140 Annie Chateau 4c0e4613d8ee10ee4e1c98180000b379 lirmm.fr annie-chateau 173624 44100-173624 https://orcid.org/0000-0003-4760-8171 https://www.idref.fr/227798856 Rodolphe Giroudeau 3eafab1248c9498dcf1c870a3b621a56 lirmm.fr rodolphe-giroudeau 172373 17662-172373 https://www.idref.fr/095605355 Mathias Weller d4090dfdea08661d21a4a05d289d7c6b u-pem.fr mathias-weller 16443 27406-16443 https://orcid.org/0000-0002-9653-3690 https://arxiv.org/a/weller_m_1 bsdr7SwAAAAJ AlCoB 2019 - 6th International Conference on Algorithms for Computational Biology 2019-05-28 2019-05-30 Berkeley United States Springer Lecture Notes in Computer Science 11488 25-38 2019 10.1007/978-3-030-18174-1_2 http://alcob2019.irdta.eu English Computer Science [cs]/Bioinformatics [q-bio.QM] Computer Science [cs]/Computational Complexity [cs.CC] Conference papers Conference papers Conference papers

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.

 Methods, Algorithms for Operations REsearch MAORE 2021-12-31
LIRMM, 161 rue Ada, 34000 Montpellier
https://www.lirmm.fr/equipes/MAORE/ Méthodes et Algorithmes pour la Bioinformatique MAB 2021-12-31
LIRMM, 161 rue Ada, 34000 Montpellier
https://www.lirmm.fr/equipes/MAB/ 02636817X 0000000122597504 https://ror.org/02feahw73 Centre National de la Recherche Scientifique CNRS 1939-10-19
https://www.cnrs.fr/ 142877891 0000000091039111 200212717U https://ror.org/04t50yk91 Laboratoire d'Informatique Gaspard-Monge LIGM 1992-01-01 2019-12-31
Université de Paris-Est Marne-la-Vallée, Cité Descartes, Bâtiment Copernic, 5 bd Descartes, 77454 Marne-la-Vallée Cedex 2
http://ligm.u-pem.fr 139590827 0000000405990488 199111950H https://ror.org/013yean28 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LIRMM 1995-01-01 2021-12-31
161 rue Ada - 34095 Montpellier
https://www.lirmm.fr 0000000120970141 https://ror.org/051escj72 Université de Montpellier UM 2021-12-31
163 rue Auguste Broussonnet - 34090 Montpellier
http://www.umontpellier.fr/ 030820499 0000000115124813 https://ror.org/02aqt9c37 Université Paris-Est Marne-la-Vallée UPEM 1991-07-22 2019-12-31
5 boulevard Descartes - Champs-sur-Marne - 77454 Marne-la-Vallée Cedex 2
http://www.u-pem.fr/ https://ror.org/02nwvxz07 École nationale des ponts et chaussées ENPC 1747-02-14 2024-12-31
École nationale des ponts et chaussées, 6-8 avenue Blaise-Pascal, Cité Descartes, Champs-sur-Marne, 77455 Marne-la-Vallée cedex 2
https://ecoledesponts.fr/ 199814079S ESIEE Paris 2016-11-25
2 boulevard Blaise PascalCité DescartesBP 9993162 Noisy-le-Grand Cedex
http://www.esiee.fr 201220485U Fédération de Recherche Bézout BEZOUT 2012-01-01
5, bd Descartes, Champs-sur-Marne77455 Marne-la-Vallée Cedex 2 – France
https://labex-bezout.fr/bezout-federation/