Premium
Parallel divide and conquer approach for the protein threading problem
Author(s) -
Yanev Nicola,
Andonov Rumen
Publication year - 2004
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.816
Subject(s) - solver , divide and conquer algorithms , computer science , shortest path problem , integer programming , equivalence (formal languages) , mathematical optimization , generalization , decomposition , graph , branch and cut , algorithm , parallel computing , theoretical computer science , mathematics , discrete mathematics , mathematical analysis , ecology , biology
For the Protein Threading Problem (PTP) we propose a network‐flow like formulation. We also show its equivalence with a generalization of the shortest path problem on a graph with a very particular structure. The underlying Mixed Integer Programming (MIP) model proves to be very appropriate for the PTP—large real‐life instances have been solved much faster by using only the MIP solver CPLEX instead of a known special‐purpose branch and bound algorithm. The properties of the MIP model permit a decomposition of the main problem into a large number of subproblems (tasks). We show that a branch and cut strategy can be efficiently applied for solving these tasks in a parallel manner, which leads to a significant reduction in the total running time. Computational experiments with large problem instances are presented. Copyright © 2004 John Wiley & Sons, Ltd.