Exact Computational Biology Algorithms with Small Parameters

Texas A&M Engineering Experiment Station, College Station TX

Investigators

Abstract

Many computational biology problems are NP-hard. For a large portion of these problems, approximation algorithms seem to be improper, since either the approximate solutions are too far away from the optimal or the high computational complexity prevents them from being practical. As a result, researchers are forced to use heuristic approaches. However, it is likely that important information is missed which could otherwise be obtained from exact algorithms. Recent study has observed that in many biological problems, it is possible to identify a parameter that is small in most instances. The notion of fixed-parameter tractability (FPT) was introduced which provides feasible exact algorithms for intractable problems with small parameters. The FPT framework has not enjoyed widespread success in computational biology since most of the research efforts are from people who were originally computer science theoreticians. Without the participation of biologists, the formulations may not be accurate and realistic. By employing biologically adequate formulations, computational techniques such as FPT stand in a perfect position to bridge the gap between theory and practice. Furthermore, the availability of huge genome sequences requires the study of a tighter class of fixed-parameter algorithms with strictly or nearly linear time. The long-term goal of the research is to bring FPT techniques into mainstream use in computational biology. The specific objectives of the project are as follows: (1) identify important computational biology problems which can be addressed by the FPT framework; (2) develop algorithms for these problems, trying to lower the time complexity as much as possible; and (3) obtain biological data and test the new algorithms on real-life data. The research will apply the algorithmic techniques that have proven to be successful in parameterized computation to solve problems that seem intractable but important and realistic in computational biology. The results of the research have the advantages of being precise and effective, compared to the traditional approaches such as approximation and heuristic algorithms. The broader impacts resulting from the project: The research is highly inter-disciplinary, which involves heavy collaborations in both computational and life sciences, and will provide an excellent educational environment for students who have mutual interests in both fields.