Multiple Alignment cost application

Question

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.

Answer 1

UPDATE

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).

3. 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.).

ORIGINAL ANSWER

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).

Answer 2

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.