<p><strong>UPDATE</strong></p>
<p>In response to comments, it seems that the question is more along the lines of:</p>
<p><strong>&quot;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?&quot;</strong></p>
<p>I have 2 responses to this:</p>
<ol>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
</ol>
<p>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).</p>
<ol start="3">
<li>The simplest application might be to come up with a quick &quot;check&quot; 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.)</li>
</ol>
<p>In summary, a lot depends on how you get that cost and what else you <em>could</em> 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.).</p>
<p><strong>ORIGINAL ANSWER</strong></p>
<p>The short answer is &quot;yes&quot;.</p>
<p>Quite frequently we are interested in measuring &quot;identity&quot; or &quot;similarity&quot; of two sequence strings. As one totally arbitrary example, <a href="https://sites.google.com/site/wiki4metagenomics/pdf/definition/operational-taxonomic-unit-otu" rel="nofollow noreferrer">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.</a> So these measures are frequently useful as heuristics.</p>
<p>Identity itself is just a length-normalized edit distance across a sequence, after all.</p>
<p>But more generally, such measures of identity or similarity can themselves be understood as cost measures, in the sense that e.g. a <a href="https://courses.cs.washington.edu/courses/cse421/15wi/slides/06dp-align-katie.pdf" rel="nofollow noreferrer">dynamic programming alignment algorithm</a> 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).</p>

CC BY-SA 4.0
2020-11-14T15:57:32.310Z
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
gcorso
CC BY-SA 4.0
2020-11-14T22:56:00.813Z
@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.
Maximilian Press
CC BY-SA 4.0
2020-11-15T10:50:28.403Z
Thank you for the answer, do you have any specific procedure in mind where it could be useful as input?
gcorso
CC BY-SA 4.0
2020-11-15T19:05:44.587Z
i'll just edit answer with response.
Maximilian Press
CC BY-SA 4.0
2020-11-14T10:44:00.493Z
2020-11-15T19:25:11.227Z
2020-11-15T19:25:11.227Z
Maximilian Press
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>I'm not saying don't try, I am saying don't look to overstate the applicability of the metric.</p>

CC BY-SA 4.0
2020-11-15T10:49:13.487Z
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)?
gcorso
CC BY-SA 4.0
2020-11-15T11:11:45.847Z
Sorry! I meant a logical error. An error that doesn't give a bug but could give an erroneous conclusion
M__
CC BY-SA 4.0
2020-11-15T11:14:30.073Z
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
M__
CC BY-SA 4.0
2020-11-14T14:41:02.280Z
2020-11-15T11:12:30.107Z
2020-11-15T11:12:30.107Z
M__
<p>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?</p>
<p>Edit: to clarify by cost I mean the cost function such as the <a href="https://en.m.wikipedia.org/wiki/Edit_distance" rel="nofollow noreferrer">edit distance</a>. 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.</p>

<phylogenetics><phylogeny><gene><sequence-analysis><multiple-sequence-alignment>
Multiple Alignment cost application
# Multiple Alignment cost application

(Asked by: username_0 on 2020-11-13)

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](https://en.m.wikipedia.org/wiki/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.

**Tags:** phylogenetics, phylogeny, gene, sequence-analysis, multiple-sequence-alignment

---

## 2 answers

### Answer by username_1 on 2020-11-14. Score: 1 | Accepted answer

**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.](https://sites.google.com/site/wiki4metagenomics/pdf/definition/operational-taxonomic-unit-otu) 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](https://courses.cs.washington.edu/courses/cse421/15wi/slides/06dp-align-katie.pdf) 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).

> **Comments:**
> **username_0**: 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  
> **username_1**: @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.  
> **username_0**: Thank you for the answer, do you have any specific procedure in mind where it could be useful as input?  
> **username_1**: i'll just edit answer with response.  

---

### Answer by username_2 on 2020-11-14. Score: 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.

> **Comments:**
> **username_0**: 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)?  
> **username_2**: Sorry! I meant a logical error. An error that doesn't give a bug but could give an erroneous conclusion  
> **username_2**: 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  

---

