On a greedy approach for genome scaffolding

BACKGROUND: Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cycles cover problem of a particular graph called the “scaffold graph”. RESULTS: We provide some NP...

Descripción completa

Detalles Bibliográficos
Autores principales: Davot, Tom, Chateau, Annie, Fossé, Rohan, Giroudeau, Rodolphe, Weller, Mathias
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2022
Materias:
Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9617463/
https://www.ncbi.nlm.nih.gov/pubmed/36309685
http://dx.doi.org/10.1186/s13015-022-00223-x
_version_ 1784820845332398080
author Davot, Tom
Chateau, Annie
Fossé, Rohan
Giroudeau, Rodolphe
Weller, Mathias
author_facet Davot, Tom
Chateau, Annie
Fossé, Rohan
Giroudeau, Rodolphe
Weller, Mathias
author_sort Davot, Tom
collection PubMed
description BACKGROUND: Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cycles cover problem of a particular graph called the “scaffold graph”. RESULTS: We provide some NP-hardness and inapproximability results on this problem. We also adapt a greedy approximation algorithm on complete graphs so that it works on a special class 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. CONCLUSION: Tests on a set of simulated instances show that our algorithm provides better results than the version on complete graphs.
format Online
Article
Text
id pubmed-9617463
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-96174632022-10-30 On a greedy approach for genome scaffolding Davot, Tom Chateau, Annie Fossé, Rohan Giroudeau, Rodolphe Weller, Mathias Algorithms Mol Biol Research BACKGROUND: Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cycles cover problem of a particular graph called the “scaffold graph”. RESULTS: We provide some NP-hardness and inapproximability results on this problem. We also adapt a greedy approximation algorithm on complete graphs so that it works on a special class 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. CONCLUSION: Tests on a set of simulated instances show that our algorithm provides better results than the version on complete graphs. BioMed Central 2022-10-29 /pmc/articles/PMC9617463/ /pubmed/36309685 http://dx.doi.org/10.1186/s13015-022-00223-x Text en © The Author(s) 2022 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/ (https://creativecommons.org/publicdomain/zero/1.0/) ) applies to the data made available in this article, unless otherwise stated in a credit line to the data.
spellingShingle Research
Davot, Tom
Chateau, Annie
Fossé, Rohan
Giroudeau, Rodolphe
Weller, Mathias
On a greedy approach for genome scaffolding
title On a greedy approach for genome scaffolding
title_full On a greedy approach for genome scaffolding
title_fullStr On a greedy approach for genome scaffolding
title_full_unstemmed On a greedy approach for genome scaffolding
title_short On a greedy approach for genome scaffolding
title_sort on a greedy approach for genome scaffolding
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9617463/
https://www.ncbi.nlm.nih.gov/pubmed/36309685
http://dx.doi.org/10.1186/s13015-022-00223-x
work_keys_str_mv AT davottom onagreedyapproachforgenomescaffolding
AT chateauannie onagreedyapproachforgenomescaffolding
AT fosserohan onagreedyapproachforgenomescaffolding
AT giroudeaurodolphe onagreedyapproachforgenomescaffolding
AT wellermathias onagreedyapproachforgenomescaffolding

Ejemplares similares