MSc Bioinformatics Data Structures and Algorithms Development 2017

Previously offered in a one-year MSc in Bioninformatics.
You can find the latest edition of the course notes here. Version history:
  • 15 June 2017 – final version for 2017.
More reading:
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to algorithms. MIT Press, Cambridge, MA, 3rd edition.
  • Baase, S. and van Gelder, A. (2000). Computer algorithms: introduction to design and analysis. Addison-Wesley, Reading, MA, 3rd edition.
  • Elloumi, M. and Zomaya, A. Y. (2011). Algorithms in computational molecular biology: techniques, approaches and applications. John Wiley & Sons, Hoboken, NJ.
See also other references cited in the text.
The picture illustrates approximate limits on where each category of time complexity can result in solutions worth waiting for; the area hints at how many useful algorithms is likely to exist within that complexity class. For example: O(kn) algorithms – bottom left – are only useful for very small n and there are very few that are useful for non-trivial problems, especially with the large data sets in bioinformatics. Algorithms that would be too slow for a particular scale of data may lead us off the picture to approximation methods.