Document Type
Thesis
Degree
Master of Science
Major
Computer Science
Date of Defense
11-16-2018
Graduate Advisor
Sharlee Climer, Department of Mathematics and Computer Science
Committee
Sharlee Climer, PhD
Badri Adhikari, PhD
Sanjiv K. Bhatia, PhD
Carlos Cruchaga, PhD
Abstract
With the advent of genetic sequencing, there was much hope of finding the inherited elements underlying complex diseases, such as late-onset Alzheimer’s disease (AD), but it has been a challenge to fully uncover the necessary information hidden in the data. A likely contributor to this failure is the fact that the pathogenesis of most complex diseases does not involve single markers working alone, but patterns of genetic markers interacting additively or epistatically. But as we move upwards beyond patterns of size two, it quickly becomes computationally infeasible to examine all combinations in the solution space. A common solution to solving this type of combinatorial optimization problem is to model it as a mixed-integer linear program (MIP) and solve it using the algorithm branch-and-cut, implemented by a commercial solver. However, with the trend of using increasing numbers of computing cores to increase computational power, there is a need for a different approach to solving MIPs that can utilize parallel environments. Here we show how a parallelized implementation of an alternative algorithm, cut-and-solve, can be used to solve this genetics problem faster than CPLEX, one of the leading commercial MIP solvers.
Recommended Citation
Chan, Michael Yip-Hin, "A Parallelized Implementation of Cut-and-Solve and a Streamlined Mixed-Integer Linear Programming Model for Finding Genetic Patterns Optimally Associated with Complex Diseases" (2018). Theses. 343.
https://irl.umsl.edu/thesis/343