Local Alignment Symmetric?

Question

[Someone]

Stupid question, I know.

Is a local alignment like Smith-Waterman typically/always considered to be symmetric? I.e. is alignment(s,t) the same as alignment(t,s)?

Thanks.

[Michael Schubert]

is this a trick question? ;-)

Answer 1

[Michael Schubert]

Consider the following two sequences as your alignment(s,t):

• ATGCAAAT
• ATCCAAA-

This is obviously not the same as alignment(t,s) because the sequences are swapped.

However, the score of a pairwise alignment is always symmetric, ie. score(alignment(s,t)) = score(alignment(t,s)). There was a question about how the score is calculated a few days back, when you read that you understand why: only the pairwise equalities or differences are considered, they have no order.

Simple proof: a scoring matrix, e.g. the BLOSUM matrices for proteins, are symmetric (although you can theoretically have an asymmetric one but then you will run into problems when scoring because of the above).

[Michael Schubert]

Yes, but then the alignment construction leads to a different alignment, which is an artefact of BLAST optimizations. This does not affect scoring.

[Someone]

thanks for the answer!

[Cjt]

I disagree. This only holds for exact alignments. Heuristics-based methods such as BLAST are dependend on input order (sequence vs. database). Seeds might get a different scoring and thus might even be considered to be not significant...

[Michael Schubert]

Yes, but then the alignment construction depends on the order of sequences, not the scoring.

Answer 2

[Michael Kuhn]

A simple implementation of the Smith-Waterman algorithm is indeed symmetric. However, in practice, this is not necessarily the case. Swapping sequences in BLAST+ may lead to different bit scores for the same alignment, because the substitution matrices are re-calculated based on the query and subject composition. Re-calculating the matrices is a numerical approximation, and may thus lead to substitution matrices that are not the same if you swap subject and query.

[Michael Schubert]

Yes, you are right. However, the scoring of the alignment is always symmetric. Algorithmic behaviour would be undefined otherwise.