Bioinformatics

This is a repository of all the algorithms covered in the Bioinformatics Course part of the Cambridge Computer Science Tripos

Algorithms Implemented:

Alignment Problems:

• Needleman-Wunsch
  • Calculate LCS and Edit Distance using this approach
• Waterman-Smith
• Nussinov RNA Folding
• Space Efficient Global Alignment (#todo cleanup)
• Method of Four Russians for LCS
  • Extend to Edit Distance, Block Alignment and Global Alignment (for very simple score matrices)

Phylogeny (Evolutionary Tree) Algorithms:

• Limb Length - O(n^2) and O(n) solutions
• Additive Phylogeny
• UPGMA
• Neighbour Joining

Additional Files Explained:

• Demos - A list of functions that can be used to demo the algorithms
• Scoring Functions - Stores different scoring matrices encapsulated into a function to use in alignment problems
• Alignment-Graph- A class for representing alignment/edit graphs
• Rosalind - Answers Rosalind Questions