2
$\begingroup$

For protein multiple sequence alignment (MSA), I am using MUSCLE (v5.1). The default setting without any specifications gives a 'bad' output even though my proteins are very similar (UniProt sequence and the corresponding PDB SEQRES sequences). 'Bad' is defined as unnecessary gaps are introduced into the sequences.

However when the super5 algorithm is used the MSA output is correct, which is described here https://drive5.com/muscle5/manual/cmd_super5.html

In addition, when I increase the gap penalty this issue can be solved but as far as I know, super4 v5.1 doesn't give you the opportunity to adjust gap penalty.

Documentation describes super5 quite similarly than the default algorithm, it "just" reduces runtime for long sequences.

Can someone please give me a hint what am I missing and/or why super5 outperforms default in terms of accuracy in such "easy" cases?

$\endgroup$
3
  • 1
    $\begingroup$ Hi there, would you mind making your example reproducible? Or at least show us the two alignments? I wonder how it is possible the gap penalty is not adjustable. Is there a reason why you want to use MUSCLE in particular? $\endgroup$ Apr 9 at 19:47
  • 1
    $\begingroup$ In general I would agree with your comment @KamilSJaron . This particular question is an exception because the underlying algorithm in context is very new and is precisely focused on the observation of the OP. I would not have been aware of the release of Muscle 5 without the OPs question. $\endgroup$
    – M__
    Apr 10 at 11:29
  • 1
    $\begingroup$ Hi! Thanks for both of you! Now I get it. To be honest, there's no particular reason for using MUSCLE. I just found it easier to implement it in Python with many cases and the output also seemed easier to parse than lets say BLAST. $\endgroup$ Apr 11 at 9:09

1 Answer 1

1
$\begingroup$

HMM Super5 is a hidden Markov model (HMM) where gap penalties and the substitution matrix are the parameters at the centre of the model. That is the answer, thats why you can't change it - it does it itself and thats its purpose. Thus one algorithm (super5) is HMM for the gap-penalty and the other one I suspect isn't.


Explanation To explain that further HMM uses observed outcomes to estimate/optimise the hidden parameters, the gap penalty being one of the two key hidden parameters. Thus the algorithm is exploring a parameter landscape through reiteration generating multi-multiple alignments (if that makes sense) using different gap penalties and considering the error between the alignments (highlighted below). The search strategy is key to the success of the output. Muscle 5 describes 'introducing variations (perturbations) into HMM parameters', I assume this is singularly with reference to super5. The parameter landscape might be quite small because it doesn't seem to be a directional search strategy in any way (there's no memory in it).

The optimisation algorithm, i.e. what is being observed is a metric called the 'pair-wise error (PWE) and pair-wise dispersion (PWD)', so what appears to be happening is the algorithm is attempting to minimise the number of gaps in an alignment and this would be compatible with your results.

Speed Super5 is breaking the alignment up into smaller alignment and solving each 'centroid' before bringing together the 'centroids'. This is an obvious strategy particularly in the era of multiple processors because it overcomes RAM bottlenecks, we are all doing that in any algorithmic context.

Overall The algorithm was not absolutely clear where PWE and the feedback loop is being deployed whether it was in the generation of centroids or bringing together the centroids and its relationship to the guide tree. There was a large reliance on BLOSSUM62 - which didn't quite make sense in the given context because the background was clear about the different substitution matrices and the impact on gap penalties.

Summary Static gap penalty parameterisation is antithesis of what super5 is about, that is why you cannot use them. The speed is clear its using parallel processing and subalignments - there are no surprises there, thats a common strategy and easy to code these days.

Final points

  • I am clear the ms has not been accepted and is available here https://www.biorxiv.org/content/10.1101/2021.06.20.449169v1.full#ref-10 . I don't want to comment further on the manuscript for several reasons, which I prefer to avoid explaining.
  • It is better to wait until the paper is published because it will likely be different.
  • The algorithm itself will unquestionably be subject to simulation studies by other authors.
  • Simulation studies were absent in the BioRXIV manuscript.
  • Muscle historically has been at the forefront of methods to increase sensitivity. If you read the Clustal Omega publication they describe the implementation of historical Muscle sensitivity improvements, in other words they must have been approved over the course of time.

Other authors are likely to investigate whether simulation conditions will result in super5 causing a 'false peak' scenario. That is the Achilles heal in any HMM.

There are certainly situations where super5 is useful in automation, that is without question. In some pipelines there is no option of checking the alignments within the pipeline because there are just to many and it stops the pipeline (human eyes the opposite of a data pipeline).

In practice optical annotation is used to overcome limitations post alignment, i.e. to resolve 'errors' in gap penalties and this is desirable because it prevents a phenomena of 'circular mathematics' which is a caution in any alignment method. The author does discuss this phenomena without calling this directly 'circular mathematics'. Any alignment algorithm can erroneously impose itself on the alignment and the metric of 'error' is extremely important in this regard. Optical analysis breaks circularisation. There is a very, very obvious solution to all this without using HMM at one extreme or 'optical analysis' at the other extreme, but one day at a time.

Example of HMM 'Circularisation' is the Achilles heal of my explanations, because I explain stuff, then reexplain it which more likely increases confusion and intersperse everything with waffle. However, I do follow a HMM style algorithm because next time I explain this it will be more honed and punchier. The hidden parameter being 'clarity' and the observed phenomena being the frequency of blank expressions, which is sought to minimise on each iteration. I do hope my search of the parameter landscape is a bit more directional than that used in Super5.


parameters looking at the documentation

-perturb SEED

It is important to do the same alignment using different random number streams. A given seed should result in the same gap pattern. If there are different gap patterns between different 'SEEDS', there's something suboptimal in the HMM and that is not good at all. If you think the Muscle 5 is implicit perfection, you don't need to check it - but its a trust thing. Its good the author made it explicit, i.e. you can set it.

The other parameters are:

-perm PERM
-consiters N
-refineiters N

The second most important parameter in my view is -perm - this is permutations on the UPGMA guide tree. If different -perm values give different alignments thats not good. It must work reasonably well because the author will have checked it.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the detailed explanation! $\endgroup$ Apr 11 at 9:16

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.