Efficient Minimum Flow Decomposition via Integer Linear Programming.
flow decomposition
integer linear programming
multiassembly and RNA assembly
network flow
Journal
Journal of computational biology : a journal of computational molecular cell biology
ISSN: 1557-8666
Titre abrégé: J Comput Biol
Pays: United States
ID NLM: 9433358
Informations de publication
Date de publication:
Nov 2022
Nov 2022
Historique:
pubmed:
20
10
2022
medline:
15
11
2022
entrez:
19
10
2022
Statut:
ppublish
Résumé
Minimum flow decomposition (MFD) is an NP-hard problem asking to decompose a network flow into a minimum set of paths (together with associated weights). Variants of it are powerful models in multiassembly problems in Bioinformatics, such as RNA assembly. Owing to its hardness, practical multiassembly tools either use heuristics or solve simpler, polynomial time-solvable versions of the problem, which may yield solutions that are not minimal or do not perfectly decompose the flow. Here, we provide the first fast and exact solver for MFD on acyclic flow networks, based on Integer Linear Programming (ILP). Key to our approach is an encoding of
Identifiants
pubmed: 36260412
doi: 10.1089/cmb.2022.0257
pmc: PMC9700332
doi:
Substances chimiques
RNA
63231-63-0
Types de publication
Journal Article
Research Support, U.S. Gov't, Non-P.H.S.
Research Support, Non-U.S. Gov't
Langues
eng
Sous-ensembles de citation
IM
Pagination
1252-1267Références
Nat Biotechnol. 2011 May 15;29(7):644-52
pubmed: 21572440
Nature. 2006 Jan 19;439(7074):344-8
pubmed: 16327776
J Comput Biol. 2013 Feb;20(2):113-23
pubmed: 23383997
BMC Bioinformatics. 2019 Apr 16;20(1):190
pubmed: 30991937
IEEE/ACM Trans Comput Biol Bioinform. 2022 Jan-Feb;19(1):48-56
pubmed: 34033544
Bioinformatics. 2014 Sep 1;30(17):2447-55
pubmed: 24813214
IEEE/ACM Trans Comput Biol Bioinform. 2015 Nov-Dec;12(6):1345-54
pubmed: 26671806
J Comput Biol. 2022 Feb;29(2):121-139
pubmed: 35041494
Genome Biol. 2016 Jan 30;17:16
pubmed: 26831908
Gene. 2005 Jan 3;344:1-20
pubmed: 15656968
Nat Rev Genet. 2013 Mar;14(3):157-67
pubmed: 23358380
IEEE/ACM Trans Comput Biol Bioinform. 2019 Mar-Apr;16(2):658-670
pubmed: 29990201
Genome Res. 2004 Mar;14(3):426-41
pubmed: 14962984
PLoS One. 2020 Jun 2;15(6):e0232946
pubmed: 32484809
Nat Biotechnol. 2010 May;28(5):511-5
pubmed: 20436464
Bioinformatics. 2018 Sep 1;34(17):2927-2935
pubmed: 29617936
BMC Bioinformatics. 2011 Apr 26;12:119
pubmed: 21521499
Genome Biol. 2021 Jan 22;22(1):44
pubmed: 33482911
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
Genomics. 2013 Nov-Dec;102(5-6):507-14
pubmed: 24161398
Nat Biotechnol. 2017 Dec;35(12):1167-1169
pubmed: 29131147
Nature. 2008 Nov 27;456(7221):470-6
pubmed: 18978772
BMC Bioinformatics. 2013;14 Suppl 5:S15
pubmed: 23734627
Nat Biotechnol. 2015 Mar;33(3):290-5
pubmed: 25690850
Nat Commun. 2021 Nov 18;12(1):6728
pubmed: 34795232
Genome Res. 2008 Dec;18(12):1865-74
pubmed: 18842824
Genome Biol. 2019 Dec 16;20(1):278
pubmed: 31842956
J Comput Biol. 2011 Nov;18(11):1693-707
pubmed: 21951053
Bioinformatics. 2012 Apr 15;28(8):1086-92
pubmed: 22368243
Genome Biol. 2014;15(10):501
pubmed: 25367074
Proc Natl Acad Sci U S A. 2011 Dec 13;108(50):19867-72
pubmed: 22135461
Bioinformatics. 2021 Jan 20;:
pubmed: 33471068
Nat Biotechnol. 2020 Jun;38(6):708-714
pubmed: 32518404
Nature. 2012 Apr 04;486(7403):395-9
pubmed: 22495314
J Comput Biol. 2022 Oct 25;:
pubmed: 36288562