A safety framework for flow decomposition problems via integer linear programming.
Journal
Bioinformatics (Oxford, England)
ISSN: 1367-4811
Titre abrégé: Bioinformatics
Pays: England
ID NLM: 9808944
Informations de publication
Date de publication:
01 11 2023
01 11 2023
Historique:
received:
15
12
2022
revised:
05
09
2023
accepted:
19
10
2023
medline:
7
11
2023
pubmed:
20
10
2023
entrez:
20
10
2023
Statut:
ppublish
Résumé
Many important problems in Bioinformatics (e.g. assembly or multiassembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding "safe" partial solutions (e.g. contigs) which are common to all solutions. Previous research on safety has focused on polynomially time solvable problems, whereas many successful and natural models are NP-hard to solve, leaving a lack of "safety tools" for such problems. We propose the first method for computing all safe solutions for an NP-hard problem, "minimum flow decomposition" (MFD). We obtain our results by developing a "safety test" for paths based on a general integer linear programming (ILP) formulation. Moreover, we provide implementations with practical optimizations aimed to reduce the total ILP time, the most efficient of these being based on a recursive group-testing procedure. Experimental results on transcriptome datasets show that all safe paths for MFDs correctly recover up to 90% of the full RNA transcripts, which is at least 25% more than previously known safe paths. Moreover, despite the NP-hardness of the problem, we can report all safe paths for 99.8% of the over 27 000 non-trivial graphs of this dataset in only 1.5 h. Our results suggest that, on perfect data, there is less ambiguity than thought in the notoriously hard RNA assembly problem. https://github.com/algbio/mfd-safety.
Identifiants
pubmed: 37862229
pii: 7325350
doi: 10.1093/bioinformatics/btad640
pmc: PMC10628435
pii:
doi:
Substances chimiques
RNA
63231-63-0
Types de publication
Journal Article
Research Support, Non-U.S. Gov't
Langues
eng
Sous-ensembles de citation
IM
Informations de copyright
© The Author(s) 2023. Published by Oxford University Press.
Références
IEEE/ACM Trans Comput Biol Bioinform. 2019 Mar-Apr;16(2):658-670
pubmed: 29990201
BMC Bioinformatics. 2010 Jan 12;11:21
pubmed: 20064276
Nat Biotechnol. 2017 Dec;35(12):1167-1169
pubmed: 29131147
BMC Bioinformatics. 2013;14 Suppl 5:S15
pubmed: 23734627
Nucleic Acids Res. 2020 Jan 8;48(D1):D682-D688
pubmed: 31691826
Algorithms Mol Biol. 2021 May 10;16(1):5
pubmed: 33971903
J Comput Biol. 1994 Winter;1(4):349-66
pubmed: 8790476
Protein Eng. 1990 Jul;3(7):565-9
pubmed: 2217130
J Comput Biol. 2022 Dec;29(12):1270-1287
pubmed: 36288562
Nucleic Acids Res. 2012 Nov 1;40(20):10073-83
pubmed: 22962361
J Comput Biol. 2022 Feb;29(2):121-139
pubmed: 35041494
Bioinformatics. 2018 Sep 1;34(17):2927-2935
pubmed: 29617936
IEEE/ACM Trans Comput Biol Bioinform. 2022 Nov-Dec;19(6):3673-3684
pubmed: 34847041
Bioinformatics. 2019 Dec 15;35(24):5086-5094
pubmed: 31147688
Nat Biotechnol. 2019 Aug;37(8):907-915
pubmed: 31375807
Genome Biol. 2020 Feb 7;21(1):30
pubmed: 32033565
Nat Biotechnol. 2015 Mar;33(3):290-5
pubmed: 25690850
Nat Commun. 2021 Nov 18;12(1):6728
pubmed: 34795232
Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53
pubmed: 11504945
Genome Res. 2022 Jul 27;:
pubmed: 35896425
Genome Biol. 2019 Dec 16;20(1):278
pubmed: 31842956
J Comput Biol. 2011 Nov;18(11):1693-707
pubmed: 21951053
Bioinformatics. 2021 Jul 19;37(12):1673-1680
pubmed: 33471068
Proc Natl Acad Sci U S A. 2011 Dec 13;108(50):19867-72
pubmed: 22135461
Bioinformatics. 2014 Sep 1;30(17):2447-55
pubmed: 24813214
J Comput Biol. 2017 Jun;24(6):590-602
pubmed: 27749096
Nat Comput Sci. 2022 Mar;2(3):148-152
pubmed: 36713932
IEEE/ACM Trans Comput Biol Bioinform. 2023 Jan-Feb;20(1):360-370
pubmed: 35104222
Comput Appl Biosci. 1993 Aug;9(4):387-96
pubmed: 8402204