Is there any biological application/case where someone would be interested in the estimated total cost of the alignment between a set of sequences (genes or amino acids) without the aligned sequence itself?

Edit: to clarify by cost I mean the cost function such as the edit distance. I have some ideas for heuristics on the multiple sequences alignment problem (which is intractable) but these would not retrieve the aligned sequence, therefore, I was wondering whether such an algorithm would be useful.


2 Answers 2



In response to comments, it seems that the question is more along the lines of:

"what are some applications where computing summary statistics associated with a specific MSA result could be useful, even if we can't return the sequences?"

I have 2 responses to this:

  1. in keeping with my original answer, I would say that it would still be useful to obtain some measure of identity, similarity, or pairwise distances between sequences (or any summary statistic about the relationship of the sequences). There are lots of applications for this level of data. I don't know whether this is something that can also be extracted from the computation, I'm a little unclear on what exactly the proposed computation is doing if it's getting a cost but not sequences.

  2. Michael says below (and I agree) that an alignment cost is likely to strongly depend on particularities of the underlying alignment model as well as the data, and things get nasty when you try to account for gaps or weirdness. Nonetheless, it's possible that a cost could be used as a sort of guide heuristic for a separate follow-up alignment procedure, to indicate a portion of parameter space which is likely to yield good results. I don't know what this looks like, but it could be simple as resource provisioning for the computation (e.g. CPUs/RAM/disk). Alternately, maybe the cost result can be a little richer and actually seed some parameters in the next computation.

Again, without more detail I'm not sure what this looks like (and I'm not an alignment expert so my suggestions wouldn't be very good anyways).

  1. The simplest application might be to come up with a quick "check" of the sequences to ask whether they are alignable in the first place. Like, as a QC step (did you forget to reverse complement?) maybe. (this assumes that the alignment in question is pretty onerous and you don't want to have to try several times.)

In summary, a lot depends on how you get that cost and what else you could get in addition to the cost. I wonder if rather than focusing on cost you can output some other richer summary of the alignment (such as e.g. sequence similarities, or gapping stats, etc.).


The short answer is "yes".

Quite frequently we are interested in measuring "identity" or "similarity" of two sequence strings. As one totally arbitrary example, in metagenomics, quite frequently two rDNA amplicons that show 97% identity are considered to be in the same species, 95% same genus, 98% same strain, etc. So these measures are frequently useful as heuristics.

Identity itself is just a length-normalized edit distance across a sequence, after all.

But more generally, such measures of identity or similarity can themselves be understood as cost measures, in the sense that e.g. a dynamic programming alignment algorithm is trying to find an optimal set of matches between two sequences, which necessarily will maximize identity. Generally what it is actually maximizing is similarity (according to some cost matrix such as e.g. BLOSUM or Jukes-Cantor or whatever).

  • $\begingroup$ Thanks for the answer do you have any application in mind where the number of strings under analysis is >2. To be clearer I have some ideas for heuristics on the multiple sequences alignment problem (which is intractable) but these would not retrieve the aligned sequence, therefore, I was wondering whether such algorithm would be useful $\endgroup$
    – gcorso
    Nov 14, 2020 at 15:57
  • $\begingroup$ @gcorso i see. i share Michael's skepticism below. it seems to me like it will be highly dependent on the specifics of parameterization and the actual sequences, such that it will be low generalizability. possibly it could be useful as an intermediate heuristic computation that is an input to another procedure, but I don't think it would be easy to interpret on its own. $\endgroup$ Nov 14, 2020 at 22:56
  • $\begingroup$ Thank you for the answer, do you have any specific procedure in mind where it could be useful as input? $\endgroup$
    – gcorso
    Nov 15, 2020 at 10:50
  • $\begingroup$ i'll just edit answer with response. $\endgroup$ Nov 15, 2020 at 19:05

I'm not a fan personally, but it is context specific. The problem is that it is heading towards optimisation, particularly algorithmic optimisation. If the alignment is the final calculation - that is cool, but the situations are select. It depends how far you want to take it.

The rationale of my skepticism is simple - if an alignment was decided on a 'maximization' criteria, be it likelihood or some other metric - the subsequent calculations based on the alignment, such as phylogenetics Jukes Cantor, Kimura 2 and 3-parameter etc ... we enter circular mathematics. The critiera that defined the alignment is the criteria we are using to perform unrelated post hoc analysis. In truth there is a degree of circular mathematics in any algorithm used to produce an alignment, but we overcome this by optical verification precisely avoid this.

In this sense the alignment is simply to establish homologous amino acid/nucleotide positions for downstream analysis. Thus optical optimisation, whilst cautioned against in every other area of bioinformatics, is considered useful in alignments because of the risk that a logical error in the alignment is amplified in downstream analysis, potentially leading to an erroneous conclusion.

Algorithms are a problem where indels are concerned and aligning across an indel. It is very easy to make errors here and 'optical analysis' would simple introduce a blockwise deletion to avoid the uncertainty, i.e. if you are not sure just chop it out - better to lose data than risk artefacts on an equivocal judgement call.

I'm not saying don't try, I am saying don't look to overstate the applicability of the metric.

  • $\begingroup$ Thank you for your answer. What do you mean when you refer to a logistical error? Would it be more useful if it could produce some sort of heat map of the regions in the sequences that are conserved (again without retrieving the discrete aligned sequence)? $\endgroup$
    – gcorso
    Nov 15, 2020 at 10:49
  • $\begingroup$ Sorry! I meant a logical error. An error that doesn't give a bug but could give an erroneous conclusion $\endgroup$
    – M__
    Nov 15, 2020 at 11:11
  • 1
    $\begingroup$ Yes a heatmap is a very good idea. Highlighting areas of mutational saturation would be very useful. The theory is a bit complex, but it is one area - particularly in phylogeny but is applicable to any analysis - where we unknowingly introduce saturated signal $\endgroup$
    – M__
    Nov 15, 2020 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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