Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications

CHAPTER 2

EFFICIENT RESTRICTED-CASE ALGORITHMS FOR PROBLEMS IN COMPUTATIONAL BIOLOGY

Patricia A. Evans and H. Todd Wareham

2.1 THE NEED FOR SPECIAL CASES

Many problems of interest, in computational biology as in other fields, have been proven to be NP-hard and so cannot be solved efficiently in general unless P = NP (the set of problems that can be solved nondeterministically in polynomial time). The large sizes and increasingly massive quantities of data make problem tractability and algorithm efficiency a critical concern for computational biology, and indeed, even polynomial-time algorithms can have difficulty coping with the large amounts of data typically encountered, necessitating the development of specialized algorithms to deal with these situations and applications.

Although intractability results are certainly a formidable obstacle to solving such problems and tend to lead researchers to use heuristics and approximations, the general form of each problem that has been proven hard rarely resembles the problem as it is applied. Reduction gadgets and constructions often describe data that does not look like the relevant biological data, leaving open the possibility that special cases that more closely resemble the intended application may be tractable.

One key aspect that may lead to tractable special cases is that the data in biological problems often have characteristics that are small or limited in size. Lengths in particular can be relatively short, such as the length ...