Uncovering the Mystery Behind Computational Biology

When we think of the term “computational biology”, we see it as such a complex field of study that non-professionals could not even approach. However, if you are an AI fan who also loses track of time when reading a new finding on the cancer cells, don’t let that mystical feeling hold you back! You can solve your biological puzzles using a computer algorithm! Many people like you and I fall in love with the interdisciplinary study of biological and computer science, and they have explored quite a lot since the end of the last century. Are you ready to join the big family? Let’s dive right into it by looking at some existing techniques that will spell out the myth, particularly the Smith-Waterman Algorithm.

First thing first, artificial intelligence covers a wide variety of algorithms besides machine learning, so don’t be limited in that sense. Okay, the type of algorithm we’ll be looking at is the Smith-Waterman Algorithm. With the advancement in DNA sequencing, many biologists have done the hard work to obtain the genomes of different proteins. With a super long string consisting of A, T, G, and C in our hands, what should we do about them? Since the genome contains all the functional, structural, and even evolutionary information, some biologists proposed to compare the DNA sequence of different proteins in the hope of finding regions of similarity. Put in the context of computer science, we are now left with a problem of string matching. Let’s take AATGCTC and TTCGAAC (they are of the same length!) as an example as we analyze the Smith-Waterman Algorithm.

If we are allowed to insert gaps for both strings, how would you do it so that two sequences align the best character by character? You can brute force attempt every possibility, but the part of you that hates to do permutational math knows there are so many cases, not to mention our problem is a simplified version already! Let’s try first constructing a matrix, with one sequence in the horizontal direction and the other vertical. This actually turns out to be a very easy way to represent all the possibilities of gap insertions, since the way we travel from the left upper corner to the right bottom corner just says it all. Taking the horizontal sequence as the reference, going diagonally means to align letters from each sequence correspondingly; going horizontally adds a gap in the second sequence and going vertically a gap in the first sequence. For instance, the pink line below denotes this:

AATG_CTC

T_TCGAA_

Okay, but you may ask: there are still so many ways to draw the line, and more importantly, is there a mathematical quantification of how good the alignment is? Programmers think of their good-old friend called dynamic programming (DP). Although to explain what DP is would go beyond the scope of the discussion (and I strongly encourage you to read more because my explanation might be inaccurate!), the idea behind it is really simple: breaking the original task into many smaller sub tasks. 

To begin with, we need a scoring system and a variable that stores the current score, called curr_S on the fly. As we take each step to draw the line, observe if two strings at the next position of interest is matching (+1), mismatching (-1), or encountering a gap (-0.5). Once we are familiar with the rule, we can start the journey. For each step taken, we can go either diagonally, horizontally, or vertically, and all we need to do is, by trial-and-error, deciding on the best strategy to move to minimize curr_S. 

Although this is not a fancy type of artificial intelligence, I hope you see the power of optimization that is primarily driven by computer science. Stay tuned for more fun on computational biology!!