{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T07:14:00Z","timestamp":1789974840152,"version":"4.0.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"S3","license":[{"start":{"date-parts":[[2019,3,1]],"date-time":"2019-03-01T00:00:00Z","timestamp":1551398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1186\/s12859-019-2648-1","type":"journal-article","created":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T09:02:49Z","timestamp":1553850169000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["RCPred: RNA complex prediction as a constrained maximum weight clique problem"],"prefix":"10.1186","volume":"20","author":[{"given":"Audrey","family":"Legendre","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Angel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fariza","family":"Tahi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,3,29]]},"reference":[{"issue":"5","key":"2648_CR1","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/S0092-8674(00)80457-2","volume":"91","author":"CC Correll","year":"1997","unstructured":"Correll CC, Freeborn B, Moore PB, Steitz TA. Metals, motifs, and recognition in the crystal structure of a 5S rRNA domain. Cell. 1997; 91(5):705\u201312.","journal-title":"Cell"},{"issue":"2","key":"2648_CR2","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1093\/bioinformatics\/btw603","volume":"33","author":"Y Kato","year":"2017","unstructured":"Kato Y, Mori T, Sato K, Maegawa S, Hosokawa H, Akutsu T. An accessibility-incorporated method for accurate prediction of RNA\u2013RNA interactions from sequence data. Bioinformatics. 2017; 33(2):202\u20139.","journal-title":"Bioinformatics"},{"issue":"9","key":"2648_CR3","doi-asserted-by":"publisher","first-page":"e0163454","DOI":"10.1371\/journal.pone.0163454","volume":"11","author":"X Xu","year":"2016","unstructured":"Xu X, Chen SJ. VfoldCPX server: Predicting RNA\u2013RNA complex structure and stability. PloS ONE. 2016; 11(9):e0163454.","journal-title":"PloS ONE"},{"issue":"1","key":"2648_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1186\/1748-7188-9-17","volume":"9","author":"S Montaseri","year":"2014","unstructured":"Montaseri S, Zare-Mirakabad F, Moghadam-Charkari N. RNA\u2013RNA interaction prediction using genetic algorithm. Algoritm Mol Biol. 2014; 9(1):17.","journal-title":"Algoritm Mol Biol"},{"issue":"1","key":"2648_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1186\/1748-7188-5-5","volume":"5","author":"R Salari","year":"2010","unstructured":"Salari R, Backofen R, Sahinalp SC. Fast prediction of RNA\u2013RNA interaction. Algoritm Mol Biol. 2010; 5(1):5.","journal-title":"Algoritm Mol Biol"},{"issue":"1","key":"2648_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/1748-7188-6-26","volume":"6","author":"R Lorenz","year":"2011","unstructured":"Lorenz R, Bernhart SH, Zu Siederdissen CH, Tafer H, Flamm C, Stadler PF, et al.ViennaRNA Package 2.0. Algoritm Mol Biol. 2011; 6(1):26.","journal-title":"Algoritm Mol Biol"},{"key":"2648_CR7","first-page":"98","volume":"15","author":"U Poolsap","year":"2010","unstructured":"Poolsap U, Kato Y, Akutsu T. Dynamic programming algorithms for RNA structure prediction with binding sites. Pac Symp Biocomput. 2010; 15:98\u2013107.","journal-title":"Pac Symp Biocomput"},{"issue":"suppl_2","key":"2648_CR8","doi-asserted-by":"publisher","first-page":"W325","DOI":"10.1093\/nar\/gkm303","volume":"35","author":"C Aksay","year":"2007","unstructured":"Aksay C, Salari R, Karakoc E, Alkan C, Sahinalp SC. taveRNA: a web suite for RNA algorithms and applications. Nucleic Acids Res. 2007; 35(suppl_2):W325\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"2","key":"2648_CR9","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","volume":"13","author":"C Alkan","year":"2006","unstructured":"Alkan C, Karakoc E, Nadeau JH, Sahinalp SC, Zhang K. RNA\u2013RNA interaction prediction and antisense RNA target search. J Comput Biol. 2006; 13(2):267\u201382.","journal-title":"J Comput Biol"},{"issue":"4","key":"2648_CR10","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1093\/bioinformatics\/btq659","volume":"27","author":"AX Li","year":"2010","unstructured":"Li AX, Marz M, Qin J, Reidys CM. RNA\u2013RNA interaction prediction based on multiple sequence alignments. Bioinformatics. 2010; 27(4):456\u201363.","journal-title":"Bioinformatics"},{"issue":"2","key":"2648_CR11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1093\/bioinformatics\/btq634","volume":"27","author":"SE Seemann","year":"2010","unstructured":"Seemann SE, Richter AS, Gesell T, Backofen R, Gorodkin J. PETcofold: predicting conserved interactions and structures of two multiple alignments of RNA sequences. Bioinformatics. 2010; 27(2):211\u20139.","journal-title":"Bioinformatics"},{"issue":"suppl_2","key":"2648_CR12","doi-asserted-by":"publisher","first-page":"W650","DOI":"10.1093\/nar\/gki473","volume":"33","author":"JH Havgaard","year":"2005","unstructured":"Havgaard JH, Lyngs\u00f8 RB, Gorodkin J. The FOLDALIGN web server for pairwise structural RNA alignment and mutual motif search. Nucleic Acids Res. 2005; 33(suppl_2):W650\u20133.","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"2648_CR13","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1016\/j.jmb.2004.10.082","volume":"345","author":"M Andronescu","year":"2005","unstructured":"Andronescu M, Zhang ZC, Condon A. Secondary structure prediction of interacting RNA molecules. J Mol Biol. 2005; 345(5):987\u20131001.","journal-title":"J Mol Biol"},{"issue":"1","key":"2648_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 1981; 9(1):133\u201348.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"2648_CR15","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/jcc.21596","volume":"32","author":"JN Zadeh","year":"2011","unstructured":"Zadeh JN, Steenberg CD, Bois JS, Wolfe BR, Pierce MB, Khan AR, et al.NUPACK: analysis and design of nucleic acid systems. J Comput Chem. 2011; 32(1):170\u20133.","journal-title":"J Comput Chem"},{"key":"2648_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2014.04.018","volume":"556","author":"W Tong","year":"2014","unstructured":"Tong W, Goebel R, Liu T, Lin G. Approximating the maximum multiple RNA interaction problem. Theor Comput Sci. 2014; 556:63\u201370.","journal-title":"Theor Comput Sci"},{"key":"2648_CR17","doi-asserted-by":"crossref","unstructured":"Mneimneh S, Ahmed SA. Gibbs\/MCMC Sampling for Multiple RNA Interaction with Sub-optimal Solutions. In: International Conference on Algorithms for Computational Biology. Springer: 2016. p. 78\u201390.","DOI":"10.1007\/978-3-319-38827-4_7"},{"issue":"12","key":"2648_CR18","doi-asserted-by":"publisher","first-page":"9542","DOI":"10.1021\/nn202666w","volume":"5","author":"E Bindewald","year":"2011","unstructured":"Bindewald E, Afonin K, Jaeger L, Shapiro BA. Multistrand RNA secondary structure prediction and nanostructure design including pseudoknots. ACS Nano. 2011; 5(12):9542\u201351.","journal-title":"ACS Nano"},{"issue":"3","key":"2648_CR19","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1021\/acs.nanolett.5b04651","volume":"16","author":"E Bindewald","year":"2016","unstructured":"Bindewald E, Afonin KA, Viard M, Zakrevsky P, Kim T, Shapiro BA. Multistrand structure prediction of nucleic acid assemblies and design of RNA switches. Nano Lett. 2016; 16(3):1726\u201335.","journal-title":"Nano Lett"},{"issue":"10","key":"2648_CR20","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1089\/cmb.2011.0094","volume":"19","author":"ME Nebel","year":"2012","unstructured":"Nebel ME, Weinberg F. Algebraic and combinatorial properties of common RNA pseudoknot classes with applications. J Comput Biol. 2012; 19(10):1134\u201350.","journal-title":"J Comput Biol"},{"issue":"2","key":"2648_CR21","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.febslet.2009.11.056","volume":"584","author":"NJ Green","year":"2010","unstructured":"Green NJ, Grundy FJ, Henkin TM. The T box mechanism: tRNA as a regulatory molecule. FEBS Lett. 2010; 584(2):318\u201324.","journal-title":"FEBS Lett"},{"issue":"2","key":"2648_CR22","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/j.bpj.2017.05.031","volume":"113","author":"CT Woods","year":"2017","unstructured":"Woods CT, Lackey L, Williams B, Dokholyan NV, Gotz D, Laederach A. Comparative visualization of the RNA suboptimal conformational ensemble in vivo. Biophys J. 2017; 113(2):290\u2013301.","journal-title":"Biophys J"},{"issue":"8","key":"2648_CR23","doi-asserted-by":"publisher","first-page":"3418","DOI":"10.1093\/nar\/gkq1186","volume":"39","author":"J Panek","year":"2010","unstructured":"Panek J, Kr\u00e1sny\u0300 L, Bobek J, Je\u017bkov\u00e1 E, Korelusova J, Vohradsky\u0300 J. The suboptimal structures find the optimal RNAs: homology search for bacterial non-coding RNAs using suboptimal RNA structures. Nucleic Acids Res. 2010; 39(8):3418\u201326.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"2648_CR24","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/s12859-018-2007-7","volume":"19","author":"A Legendre","year":"2018","unstructured":"Legendre A, Angel E, Tahi F. Bi-objective integer programming for RNA secondary structure prediction with pseudoknots. BMC Bioinformatics. 2018; 19(1):13.","journal-title":"BMC Bioinformatics"},{"issue":"13","key":"2648_CR25","doi-asserted-by":"publisher","first-page":"i85","DOI":"10.1093\/bioinformatics\/btr215","volume":"27","author":"K Sato","year":"2011","unstructured":"Sato K, Kato Y, Hamada M, Akutsu T, Asai K. IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming. Bioinformatics. 2011; 27(13):i85\u201393.","journal-title":"Bioinformatics"},{"issue":"3","key":"2648_CR26","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1093\/bioinformatics\/btu649","volume":"31","author":"S Janssen","year":"2014","unstructured":"Janssen S, Giegerich R. The RNA shapes studio. Bioinformatics. 2014; 31(3):423\u20135.","journal-title":"Bioinformatics"},{"issue":"21","key":"2648_CR27","doi-asserted-by":"publisher","first-page":"2738","DOI":"10.1093\/bioinformatics\/bts519","volume":"28","author":"A Wenzel","year":"2012","unstructured":"Wenzel A, Akbas\u0307li E, Gorodkin J. RIsearch: fast RNA\u2013RNA interaction search using a simplified nearest-neighbor energy model. Bioinformatics. 2012; 28(21):2738\u201346.","journal-title":"Bioinformatics"},{"issue":"24","key":"2648_CR28","doi-asserted-by":"publisher","first-page":"2849","DOI":"10.1093\/bioinformatics\/btn544","volume":"24","author":"A Busch","year":"2008","unstructured":"Busch A, Richter AS, Backofen R. IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions. Bioinformatics. 2008; 24(24):2849\u201356.","journal-title":"Bioinformatics"},{"issue":"18","key":"2648_CR29","doi-asserted-by":"publisher","first-page":"i460","DOI":"10.1093\/bioinformatics\/btq372","volume":"26","author":"Y Kato","year":"2010","unstructured":"Kato Y, Sato K, Hamada M, Watanabe Y, Asai K, Akutsu T. RactIP: fast and accurate prediction of RNA\u2013RNA interaction using integer programming. Bioinformatics. 2010; 26(18):i460\u20136.","journal-title":"Bioinformatics"},{"key":"2648_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems.","author":"RM Karp","year":"1972","unstructured":"Karp RM. Reducibility among combinatorial problems.Boston: Springer; 1972."},{"issue":"3","key":"2648_CR31","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu Q, Hao JK. A review on algorithms for maximum clique problems. Eur J Oper Res. 2015; 242(3):693\u2013709.","journal-title":"Eur J Oper Res"},{"issue":"9","key":"2648_CR32","first-page":"4800","volume":"219","author":"U Benlic","year":"2013","unstructured":"Benlic U, Hao JK. Breakout local search for the quadratic assignment problem. Appl Math Comput. 2013; 219(9):4800\u201315.","journal-title":"Appl Math Comput"},{"issue":"suppl_1","key":"2648_CR33","doi-asserted-by":"publisher","first-page":"D280","DOI":"10.1093\/nar\/gkp892","volume":"38","author":"DH Turner","year":"2009","unstructured":"Turner DH, Mathews DH. NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res. 2009; 38(suppl_1):D280\u20132.","journal-title":"Nucleic Acids Res"},{"key":"2648_CR34","volume-title":"Proceedings\u2013Estonian Academy of Sciences Physics Mathematics, vol. 54(2)","author":"D Kumlander","year":"2005","unstructured":"Kumlander D. Problems of optimization: an exact algorithm for finding a maximum clique optimized for dense graphs. In: Proceedings\u2013Estonian Academy of Sciences Physics Mathematics, vol. 54(2). Tallinn Estonia: Estonian Academy Publishers: 2005. p. 79."},{"key":"2648_CR35","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S1571-0653(05)80045-9","volume":"3","author":"PR \u00d6sterg\u00e5rd","year":"1999","unstructured":"\u00d6sterg\u00e5rd PR. A new algorithm for the maximum-weight clique problem. Electron Notes Discrete Math. 1999; 3:153\u20136.","journal-title":"Electron Notes Discrete Math"},{"key":"2648_CR36","volume-title":"Combinatorial branch-and-bound for the maximum weight independent set problem. Texas A&M University, Citeseer","author":"JS Warren","year":"2006","unstructured":"Warren JS, Hicks IV. Combinatorial branch-and-bound for the maximum weight independent set problem. Texas A&M University, Citeseer. Pennsylvania State University: Citeseer; 2006."},{"issue":"2","key":"2648_CR37","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s10732-007-9026-2","volume":"14","author":"W Pullan","year":"2008","unstructured":"Pullan W. Approximating the maximum vertex\/edge weighted clique using local search. J Heuristics. 2008; 14(2):117\u201334.","journal-title":"J Heuristics"},{"issue":"1","key":"2648_CR38","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/s10479-012-1124-3","volume":"196","author":"Q Wu","year":"2012","unstructured":"Wu Q, Hao JK, Glover F. Multi-neighborhood tabu search for the maximum weight clique problem. Ann Oper Res. 2012; 196(1):611\u201334.","journal-title":"Ann Oper Res"},{"issue":"1-2","key":"2648_CR39","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10732-006-3750-x","volume":"12","author":"A Singh","year":"2006","unstructured":"Singh A, Gupta AK. A hybrid heuristic for the maximum clique problem. J Heuristics. 2006; 12(1-2):5\u201322.","journal-title":"J Heuristics"},{"issue":"4","key":"2648_CR40","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1137\/S1052623400381413","volume":"12","author":"A Massaro","year":"2002","unstructured":"Massaro A, Pelillo M, Bomze IM. A complementary pivoting approach to the maximum weight clique problem. SIAM J Optim. 2002; 12(4):928\u201348.","journal-title":"SIAM J Optim"},{"key":"2648_CR41","volume-title":"Local Search Algorithms.","author":"LJK Aarts Emile","year":"1997","unstructured":"Aarts Emile LJK. Local Search Algorithms.Hoboken: Wiley; 1997."},{"key":"2648_CR42","volume-title":"Tabu search Fred Glover, Manuel Laguna","author":"Glover F","year":"1997","unstructured":"Glover F. Tabu search Fred Glover, Manuel Laguna. Boston: Kluwer Academic Publishers; 1997."},{"issue":"1","key":"2648_CR43","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1186\/1471-2105-9-340","volume":"9","author":"M Andronescu","year":"2008","unstructured":"Andronescu M, Bereg V, Hoos HH, Condon A. RNA STRAND: the RNA secondary structure and statistical analysis database. BMC Bioinformatics. 2008; 9(1):340.","journal-title":"BMC Bioinformatics"},{"key":"2648_CR44","unstructured":"Djelloul M. Algorithmes de graphes pour la recherche de motifs r\u00e9currents dans les structures tertiaires d\u2019ARN. Universit\u00e9 Paris Sud-Paris XI: HAL; 2009."},{"issue":"12","key":"2648_CR45","doi-asserted-by":"publisher","first-page":"i207","DOI":"10.1093\/bioinformatics\/bts226","volume":"28","author":"V Reinharz","year":"2012","unstructured":"Reinharz V, Major F, Waldisp\u00fchl J. Towards 3D structure prediction of large RNA molecules: an integer programming framework to insert local 3D motifs in RNA secondary structure. Bioinformatics. 2012; 28(12):i207\u201314.","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2648-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-2648-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2648-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,28]],"date-time":"2020-03-28T00:05:10Z","timestamp":1585353910000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-2648-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3]]},"references-count":45,"journal-issue":{"issue":"S3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["2648"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-2648-1","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3]]},"assertion":[{"value":"29 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"128"}}