Mod/Resc parsimony inference

DOI10.1007/978-3-642-13509-5_19MaRDI QIDQ3575248zbMATH OpenOpenAlexFDO

Authors Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstädter, Max Reuter, Olivier Duron, Marie-France Sagot

Publication date 26 July 2010

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.1292

zbMATH Keywords

biclique edge coveringbipartite graphBoolean matrixcomputational biologyfixed-parameter tractabilitygraph theorykernelizationNP-completeness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08) Ecology (92D40)

Abstract: We address in this paper a new computational biology problem that aims at understanding a mechanism that could potentially be used to genetically manipulate natural insect populations infected by inherited, intra-cellular parasitic bacteria. In this problem, that we denote by extsc{Mod/Resc Parsimony Inference}, we are given a boolean matrix and the goal is to find two other boolean matrices with a minimum number of columns such that an appropriately defined operation on these matrices gives back the input. We show that this is formally equivalent to the extsc{Bipartite Biclique Edge Cover} problem and derive some complexity results for our problem using this equivalence. We provide a new, fixed-parameter tractability approach for solving both that slightly improves upon a previously published algorithm for the extsc{Bipartite Biclique Edge Cover}. Finally, we present experimental results where we applied some of our techniques to a real-life data set.

Recommendations

• Mod/Resc parsimony inference: theory and application
• The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability
• Extended islands of tractability for parsimony haplotyping
• Complete Parsimony Haplotype Inference Problem and Algorithms
• Efficient approximation for restricted biclique cover problems

Cited in

(1)

• Mod/Resc parsimony inference: theory and application

This page was built for publication: Mod/Resc parsimony inference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575248)