Algorithms for the quantitative Lock/Key model of cytoplasmic incompatibility

Autor: Calamoneri, Tiziana, Gastaldello, Mattia, Mary, Arnaud, Sagot, Marie-France, Sinaimeri, Blerina
Přispěvatelé: Dipartimento di Ingegneria informatica automatica e gestionale [Roma] (DIAG UNIROMA), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dipartimento di Ingegneria informatica automatica e gestionale (DIAG), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Algorithms for Molecular Biology
Algorithms for Molecular Biology, 2020, pp.1-16. ⟨10.1186/s13015-020-00174-1⟩
Algorithms for Molecular Biology, Vol 15, Iss 1, Pp 1-16 (2020)
Algorithms for Molecular Biology, BioMed Central, 2020, pp.1-16. ⟨10.1186/s13015-020-00174-1⟩
Algorithms for Molecular Biology : AMB
ISSN: 1748-7188
DOI: 10.1186/s13015-020-00174-1⟩
Popis: International audience; Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite Wolbachia 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.
Databáze: OpenAIRE
Externí odkaz: