Biology Stack Exchange is a question and answer site for biology researchers, academics, and students. It only takes a minute to sign up.
Sign up to join this community
Assume that you have two implementations of the Smith–Waterman algorithm (with what ever heuristic they apply to speed up) for local sequence alignment of genomic sequences.
I would like to know if one can be certain that these implementations do a good job of aligning (i.e the program has been correctly written). How do I benchmark this?
There are only two possibilities for Smith-Waterman alignment with a given cost matrix. It's either right or it's not.
Honestly, whatever you're using, it's really really unlikely that a pure Smith-Waterman implementation is wrong. It's not that complicated, really. There are a lot of heuristic improvements on Smith-Waterman, but if you're both a) sure you don't want to test them b) sure they're not being used, you can always generate lots of random sequences and align them in pairs. If any pair doesn't align with the same score in the same way, something is wrong and you should investigate further.
I imagine that technically your question can only be answered on a computing science Stack Exchange. The pragmatic biology answer is there is no problem. This is such a well established algorithm that the implementation on any reputable site or from any reputable provider is likely to be OK. No heuristic is involved so if you compare different implementations you should get similar answers. I say similar rather than identical because there may be more than one alignment with the same score but only one is selected. Generally it makes no difference.
I suppose there is one aspect of the Smith–Waterman algorithm that could differ between implementations, but it is one for which you, the user, will have the ultimate responsibility — the scoring system. Your basic assumption is that two sequences are related, and you are asking the program to give you the pairwise alignment that ‘best’ expresses that relatedness. ‘Best’ in the program translates into the highest score on a system that assigns a different value to the alignment of different pairs of all 20 amino acids (a comparison matrix for proteins) and specific penalties for the introduction of a gap (to allow for an insertion or deletion) and the extension of a gap once introduced. The implementations offer default values (I imagine these are similar in most programs) but its up to you to decide whether they are appropriate for the sequences that you are comparing, and to change them if necessary.
What are your options and when might it be necessary to exercise them? You can choose from different comparison matrices derived from aligning blocks of sequences for the same protein in organisms of different evolutionary separation. These matrices differ because some amino acid changes require only a single base change in the codon, whereas others require changes at all three positions of a codon,. The latter are less likely to occur over short evolutionary time spans (e.g. between mouse and rat) than at longer ones (e.g. between mouse and bacterium). So ideally you should employ the comparison matrix most appropriate to the sequences you are comparing.
Circumstances where you might wish to change the gap penalties or even customize the comparison tables are, admittedly, esoteric, but I would advise that it is better to think about the applicability of the scoring system to your biological problem than to worry that someone might have made a hash of implementing the computer algorithm.
