Abstract—Quite recently, considerable attention has been paid to finding the distinction between driver mutations that lead to tumorigenesis and passenger mutations that are neutral and do not play any role in the cancer proliferation. The main objective of this work is to come up with a new method to solve “The Maximum Weight Submatrix Problem”. To that end, we introduce a new constraint named “approximate exclusivity” that helps to determine precisely the number of mutations that each patient has in the pathway. Depending on this constraint, we present a novel algorithm that detects driver mutated pathways based on an exact approach. We describe the details about our algorithm, then we compare the results with a Genetic Algorithm and a Binary Linear Programming model in both simulated and genetic data. Our exact algorithm has shown a good performance in terms of maximizing the weight and detecting all the possible driver pathways.
 
Index Terms—driver pathways, maximum weight submatrix problem, exact algorithm, genetic algorithm, binary linear programming, glioblastoma multiform