Algorithmic complexity in Computational Biology.

Computational problems can be classified according to their algorithmic complexity, which is defined based on how the computational resources needed to solve the problem scale with the problem size. In particular, computationally intractable problems are often solved through heuristics or approximations so to overcome the search costs associated with exhaustive approaches. The computational complexity of the algorithms that are used in Computational Biology is an often neglected property, rarely surveyed for broad audiences. The aim of this work is to look over the main current algorithmic solutions to intractable problems in Computational Biology, highlighting the importance of High Performance Computing (HPC) and heuristic solutions in this area.