{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:34Z","timestamp":1740144514815,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T00:00:00Z","timestamp":1595376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T00:00:00Z","timestamp":1595376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ANR","award":["ANR-15-CE40-0009"],"award-info":[{"award-number":["ANR-15-CE40-0009"]}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 2012C4E3KT"],"award-info":[{"award-number":["PRIN 2012C4E3KT"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100015564","name":"Universita Italo-Francese","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100015564","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite <jats:italic>Wolbachia<\/jats:italic> of its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the phenomenon. We consider in this paper the quantitative Lock-Key model which currently represents a good hypothesis that is consistent with the data available. CI is in this case modelled as the problem of covering the edges of a bipartite graph with the minimum number of chain subgraphs. This problem is already known to be NP-hard, and we provide an exponential algorithm with a non trivial complexity. It is frequent that depending on the dataset, there may be many optimal solutions which can be biologically quite different among them. To rely on a single optimal solution may therefore be problematic. To this purpose, we address the problem of enumerating (listing) all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time. Interestingly, in order to solve the above problems, we considered also the problem of enumerating all the maximal chain subgraphs of a bipartite graph and improved on the current results in the literature for the latter. Finally, to demonstrate the usefulness of our methods we show an application on a real dataset.<\/jats:p>","DOI":"10.1186\/s13015-020-00174-1","type":"journal-article","created":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T09:07:57Z","timestamp":1595408877000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for the quantitative Lock\/Key model of cytoplasmic incompatibility"],"prefix":"10.1186","volume":"15","author":[{"given":"Tiziana","family":"Calamoneri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mattia","family":"Gastaldello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Mary","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie-France","family":"Sagot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9797-7592","authenticated-orcid":false,"given":"Blerina","family":"Sinaimeri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,22]]},"reference":[{"issue":"1","key":"174_CR1","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1146\/annurev.genet.41.110306.130354","volume":"42","author":"LR Serbus","year":"2008","unstructured":"Serbus LR, Casper-Lindley C, Landmann F, Sullivan W. The genetics and cell biology of Wolbachia-host interactions. Ann Rev Genet. 2008;42(1):683\u2013707.","journal-title":"Ann Rev Genet"},{"issue":"1529","key":"174_CR2","doi-asserted-by":"publisher","first-page":"2185","DOI":"10.1098\/rspb.2003.2475","volume":"270","author":"MS Hunter","year":"2003","unstructured":"Hunter MS, Perlman SJ, Kelly SE. A bacterial symbiont in the bacteroidetes induces cytoplasmic incompatibility in the parasitoid wasp Encarsia pergandiella. Proc R Soc Lond Ser B Biol Sci. 2003;270(1529):2185\u201390.","journal-title":"Proc R Soc Lond Ser B Biol Sci"},{"key":"174_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1038\/sj.hdy.6800881","volume":"98","author":"T Gotoh","year":"2007","unstructured":"Gotoh T, Noda H, Ito S. Cardinium symbionts cause cytoplasmic incompatibility in spider mites. Heredity. 2007;98:13\u201320.","journal-title":"Heredity"},{"issue":"42","key":"174_CR4","doi-asserted-by":"publisher","first-page":"15042","DOI":"10.1073\/pnas.0403853101","volume":"101","author":"S Zabalou","year":"2004","unstructured":"Zabalou S, Riegler M, Theodorakopoulou M, Stauffer C, Savakis C, Bourtzis K. Wolbachia-induced cytoplasmic incompatibility as a means for insect pest population control. Proc Natl Acad Sci. 2004;101(42):15042\u20135. https:\/\/doi.org\/10.1073\/pnas.0403853101.","journal-title":"Proc Natl Acad Sci"},{"key":"174_CR5","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1146\/annurev.ento.42.1.587","volume":"42","author":"JH Werren","year":"1997","unstructured":"Werren JH. Biology of Wolbachia. Ann Rev Entomol. 1997;42:587\u2013609.","journal-title":"Ann Rev Entomol"},{"issue":"1","key":"174_CR6","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1086\/670612","volume":"182","author":"I Nor","year":"2013","unstructured":"Nor I, Engelst\u00e4dter J, Duron O, Reuter M, Sagot M-F, Charlat S. On the genetic architecture of cytoplasmic incompatibility: inference from phenotypic data. Am Nat. 2013;182(1):15\u201324.","journal-title":"Am Nat"},{"issue":"3","key":"174_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1002\/bies.10234","volume":"25","author":"D Poinsot","year":"2003","unstructured":"Poinsot D, Charlat S, Herv\u00e9 M. On the mechanism of wolbachia-induced cytoplasmic incompatibility: Confronting the models with the facts. BioEssays 25(3), 259\u2013265","journal-title":"BioEssays"},{"issue":"5","key":"174_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0019757","volume":"6","author":"B Bossan","year":"2011","unstructured":"Bossan B, Koehncke A, Hammerstein P. A new model and method for understanding Wolbachia-induced cytoplasmic incompatibility. PLOS ONE. 2011;6(5):1\u20139.","journal-title":"PLOS ONE"},{"key":"174_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.ic.2011.03.008","volume":"213","author":"I Nor","year":"2012","unstructured":"Nor I, Hermelin D, Charlat S, Engelstadter J, Reuter M, Duron O, Sagot M-F. Mod\/resc parsimony inference: theory and application. Inf Comput. 2012;213:23\u201332.","journal-title":"Inf Comput"},{"issue":"14","key":"174_CR10","doi-asserted-by":"publisher","first-page":"1826","DOI":"10.1016\/j.dam.2007.03.017","volume":"155","author":"VMF Dias","year":"2007","unstructured":"Dias VMF, de Figueiredo CMH, Szwarcfiter JL. On the generation of bicliques of a graph. Discrete Appl Math. 2007;155(14):1826\u201332.","journal-title":"Discrete Appl Math"},{"doi-asserted-by":"crossref","unstructured":"Makino K, Uno T. New algorithms for enumerating all maximal cliques. In: SWAT 2004, Lecture notes in computer science, vol. 3111, Berlin, Heidelberg: Springer; p. 260\u201372. 2004.","key":"174_CR11","DOI":"10.1007\/978-3-540-27810-8_23"},{"issue":"1\u20133","key":"174_CR12","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.tcs.2005.01.014","volume":"337","author":"VMF Dias","year":"2005","unstructured":"Dias VMF, de Figueiredo CMH, Szwarcfiter JL. Generating bicliques of a graph in lexicographic order. Theor Comput Sci. 2005;337(1\u20133):240\u20138.","journal-title":"Theor Comput Sci"},{"issue":"6","key":"174_CR13","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T Eiter","year":"1995","unstructured":"Eiter T, Gottlob G. Identifying the minimal transversals of a hypergraph and related problems. SIAM J Comput. 1995;24(6):1278\u2013304.","journal-title":"SIAM J Comput"},{"issue":"3","key":"174_CR14","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson DS, Yannakakis M, Papadimitriou CH. On generating all maximal independent sets. Inf Process Lett. 1988;27(3):119\u201323.","journal-title":"Inf Process Lett"},{"issue":"3","key":"174_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1023\/A:1006211307442","volume":"15","author":"S Felsner","year":"1998","unstructured":"Felsner S, Gustedt J, Morvan M. Interval reductions and extensions of orders: bijections to chains in lattices. Order. 1998;15(3):221\u201346.","journal-title":"Order"},{"key":"174_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin FV, Kratsch D. Exact exponential algorithms. New York: Springer; 2010."},{"issue":"1","key":"174_CR17","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon JW, Moser L. On cliques in graphs. Israel J Math. 1965;3(1):23\u20138.","journal-title":"Israel J Math"},{"issue":"1","key":"174_CR18","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.tcs.2007.04.006","volume":"381","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt A, Eschen EM, Sritharan R. The induced matching and chain subgraph cover problems for convex bipartite graphs. Theor Comput Sci. 2007;381(1):260\u20135.","journal-title":"Theor Comput Sci"},{"issue":"1","key":"174_CR19","first-page":"85","volume":"205","author":"C-W Yu","year":"1998","unstructured":"Yu C-W, Chen G-H, Ma T-H. On the complexity of the k-chain subgraph cover problem. Theor Comput Sci. 1998;205(1):85\u201398.","journal-title":"Theor Comput Sci"},{"issue":"3","key":"174_CR20","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M Yannakakis","year":"1982","unstructured":"Yannakakis M. The complexity of the partial order dimension problem. SIAM J Algebr Discrete Methods. 1982;3(3):351\u20138.","journal-title":"SIAM J Algebr Discrete Methods"},{"issue":"3","key":"174_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00373-010-0922-0","volume":"26","author":"A Abueida","year":"2010","unstructured":"Abueida A, Busch AH, Sritharan R. A min-max property of chordal bipartite graphs with applications. Graphs Combinat. 2010;26(3):301\u201313.","journal-title":"Graphs Combinat"},{"issue":"2","key":"174_CR22","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund A, Husfeldt T, Koivisto M. Set partitioning via inclusion-exclusion. SIAM J Comput. 2009;39(2):546\u201363.","journal-title":"SIAM J Comput"},{"key":"174_CR23","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern graph theory. Graduate texts in mathematics","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s B. Modern graph theory. Graduate texts in mathematics, vol. 184. Berlin: Springer;1998. p. 394"},{"unstructured":"Freire A, Nor I, Acu\u00f1a V, Ferreira CE, Crescenzi P, Moreno E, Charlat S, Sim\u00f5es P, Sagot M-F. Private Communication. 2012","key":"174_CR24"},{"issue":"3","key":"174_CR25","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"ML Fredman","year":"1996","unstructured":"Fredman ML, Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms. J Algor. 1996;21(3):618\u201328.","journal-title":"J Algor"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00174-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-020-00174-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00174-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T23:20:39Z","timestamp":1626909639000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-00174-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,22]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["174"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-00174-1","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2020,7,22]]},"assertion":[{"value":"23 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"14"}}