Are you troubled by not finding the perfect match?

Well, having discussed sequence alignment for the last couple of weeks I thought this would be a good time to talk about how finding a perfect match works. That is, how to find a sequence, like this one
TATCACT

… inside another (database of) other sequence(s):
TTAGCTACTTACTAGCGTCATATCACTTATCTAGCATTCATCTGTACGTATCTAC
TTAGCTACTTACTAGCGTCATATCCCTTATCTAGCATTCATCTGTACGTATCTAC
TTATCGACTATCATGACTATAGCTATCTGAGGTCAGTCGTTACTATATTATTATCTGCGCGCGATTACGTAGCTACTTACTAGCGTCATATCCCTTATCTAGCATTCATCTGTACGTATCTAC

… and of course you know you just use Command-F. But how do we find a matching string that’s 25 bases long, in a list of 100,000,000,000 bases? And then, how do you find all of them? That’s the question that we have to be able to answer, if we want to, say, do BLAST.
Given that sequence alignment is essentially a bit slow (it’s O(n^2): takes roughly an amount of time proportional to the square of the sequence lengths), we need to use a fast method to find matching strings, that doesn’t have to use alignment.

I’ll talk about these things on Thursday of this week:

See you then! (I hope…)

Cheers
Mike

Michael Charleston
Associate Professor in Bioinformatics
School of Physical Sciences
University of Tasmania
AUSTRALIA
phone: +61 3 6226 2444



University of Tasmania Electronic Communications Policy (December, 2014).
This email is confidential, and is for the intended recipient only. Access, disclosure, copying, distribution, or reliance on any of it by anyone outside the intended recipient organisation is prohibited and may be a criminal offence. Please delete if obtained in error and email confirmation to the sender. The views expressed in this email are not necessarily the views of the University of Tasmania, unless clearly intended otherwise.