1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is this a question on DNA? Could you give some more context to the question? Better tagging may help too. $\endgroup$ – AliceD Mar 18 '16 at 20:50
  • $\begingroup$ They don't apply any heuristic to speed it up. The essential feature of the Dynamic programming algorithm is it gives you one of the correct answers. You don't have to speed it up because it runs in real time. This is an important point and I suggest you modify your question. $\endgroup$ – David Mar 18 '16 at 21:35
  • $\begingroup$ I am not sure that 'i.e.' is a right word. Alignment quality is a matter of substitution matrices and gap penalties and it has nothing to deal with correctness. $\endgroup$ – Maxim Kuleshov Mar 18 '16 at 21:37
  • $\begingroup$ You need to clarify the question. Smith-Watermann is a specific algorithm. There are no other implementations of it. There can be additional steps that are used in conjunction with SW and unless you atleast tell the names of these packages, we cannot comment on how one of them may be better than the other. As far as comparison goes, the one that does your job reasonable well in less time is the better implementation. To check if the program has been correctly written you should look at its source code. That is essentially bug finding. $\endgroup$ – WYSIWYG Mar 19 '16 at 7:41
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.