THE UNIFORM MINIMUM-ONES 2SAT PROBLEMAND ITS APPLICATION TO HAPLOTYPECLASSIFICATION

Analyzing genomic data for finding those gene variationswhich are responsible for hereditary diseases is one of the great challengesin modern bioinformatics. In many living beings (including thehuman), every gene is present in two copies, inherited from the twoparents, the so-called haplotypes. In this paper, we propose a simplecombinatorial model for classifying the set of haplotypes in a populationaccording to their responsibility for a certain genetic disease.This model is based on the minimum-ones 2SAT problem with uniformclauses. The minimum-ones 2SAT problem asks for a satisfying assignmentto a satisfiable formula in 2CNF which sets a minimum numberof variables to true. This problem is well-known to be NP-hard, evenin the case where all clauses are uniform, i.e., do not contain a positiveand a negative literal. We analyze the approximability and present thefirst non-trivial exact algorithm for the uniform minimum-ones 2SATproblem with a running time of O(1.21061n) on a 2SAT formula with nvariables. We also show that the problem is fixed-parameter tractableby showing that our algorithm can be adapted to verify in O∗(2k) timewhether an assignment with at most k true variables exists