Answers.Body: <p>All Chris_Rands said is correct: you set the probability of $X\to Y$ and $Y\to X$ to 0 to forbid adjacent insertions/deletions in the alignment. A lot of textbooks including some classical ones use this rule, but in fact, the rule is questionable. It is easier to see this from Smith-Waterman alignment under the affine gap penalty, which is largely the non-probabilistic view of paired HMM.</p>
  
  <p>With the affine gap penalty, a gap of length $k&gt;0$ is scored as
  $$
  g(k)=-(d+k\cdot e)
  $$
  where $d\ge0$ is the gap open penalty and $e&gt;0$ is the gap extension penalty. Suppose we are using a simple scoring matrix where a mismatch gets $-b$, $b&gt;0$. We may see an insertion immediately followed by a deletion (and vice versa) if $b&gt;2e$. It is actually not so difficult for this to happen. For example, for the human-mouse alignment (see the <a href="https://www.ncbi.nlm.nih.gov/pubmed/12529312" rel="nofollow noreferrer">blastz paper</a>), $e=30$ and $b$ is ranged from 31 to 125. It is possible that an $X\to Y$ transition is preferred in the alignment.</p>
  
  <p>Theoretically speaking, it makes more sense to consider immediate transitions between insertions and deletions. In practice, though, the difference between allowing/disallowing such transitions is probably minor most of time.</p>
  
  <p>EDIT: on Chris' example</p>
  
  <pre><code>CGTACGTAGAGGAATGCCCCCCCCC--------AGCAACGTAGCAT     
  CGTACGTAGAGGAATG---------TTTTTTTTAGCAACGTAGCAT
  </code></pre>
  
  <p>If we use a scoring matrix with $b&gt;2e$ but disallow adjacent ins-to-del transitions, we will probably end up with an alignment like</p>
  
  <pre><code>CGTACGTAGAGGAATGCCCCCCCCC-------AGCAACGTAGCAT     
  CGTACGTAGAGGAATG--------TTTTTTTTAGCAACGTAGCAT
  </code></pre>
  
  <p>This alignment score will be lower.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-12T18:51:01.613Z
Answers.LastActivityDate: 2018-09-13T11:52:40.520Z
Answers.LastEditDate: 2018-09-13T11:52:40.520Z
Answers.UserDisplayName: user172818
Answers.Body: <p>If I understand your question correctly, then I think for case of pairwise alignment, there is a simple explanation.</p>
  
  <p>I believe the key insight is that: <em>a mismatch should always score better than a gap</em>.*</p>
  
  <p>This follows biologically since the insertion/deletion (indel) rate is roughly 1/10th that of the substitution rate (i.e. the occurrence of single nucleotide changes), at least in vertebrates. (This varies across the tree of life but I think the substitution rate virtually always exceeds the indel rate.)</p>
  
  <p>To understand why this matters, consider an example:</p>
  
  <pre><code>ATG-AG
  ATGT-G
  </code></pre>
  
  <p>This is an 'impossible alignment' under the probabilities you gave since here we have a transition from a gap-residue alignment to a residue-gap.</p>
  
  <p>However, under our assumption that mismatches are more likely biologically than indels, the correct alignment should be:</p>
  
  <pre><code>ATGAG
  ATGTG
  </code></pre>
  
  <p>Indeed, the latter does look like a better alignment.</p>
  
  <p>This also follows for more complex examples, so this:</p>
  
  <pre><code>ATG--AAG
  ATGTT-AG
  </code></pre>
  
  <p>Becomes this:</p>
  
  <pre><code>ATG-AAG
  ATGTTAG
  </code></pre>
  
  <p>(Or this:</p>
  
  <pre><code>ATGA-AG
  ATGTTAG
  </code></pre>
  
  <p>)</p>
  
  <p>* Strictly, I mean a substitution should score better than an indel (with the associated gap opening and extension penalties). In fact, for the assumption to always be true, a run of mismatches should still score worse than a single indel. This may not always be a correct assumption, consider this example below, is the true alignment case 1) or 2) or something else? Or is in fact a global alignment bad here and this should be split into 2 local alignments? Is there a likely biological mutational event that could explain this? I ask these questions just to point out it is not black-and-white, I don't have clear answers</p>
  
  <p>1)</p>
  
  <pre><code>CGTACGTAGAGGAATGCCCCCCCCC--------AGCAACGTAGCAT     
  CGTACGTAGAGGAATG---------TTTTTTTTAGCAACGTAGCAT
  </code></pre>
  
  <p>2)</p>
  
  <pre><code>CGTACGTAGAGGAATGCCCCCCCCCAGCAACGTAGCAT     
  CGTACGTAGAGGAATGTTTTTTTT-AGCAACGTAGCAT
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-11T09:09:48.950Z
Answers.LastActivityDate: 2018-09-12T08:27:09.803Z
Answers.LastEditDate: 2018-09-12T08:27:09.803Z
Answers.UserDisplayName: Chris_Rands
Body: <p>I am learning about applying Markov model to sequence alignment. The prof says that the transition probabilities from a gap-residue alignment to a residue-gap alignment and vice versa are both 0. Is there any biological/mathematical reason behind this statement? Why are the (X,Y) and (Y,X) cell 0? This is a lecture slide of lecture 1, week 4 of the "Bioinformatics: Introdcution and Methods" course on coursera.
  <a href="https://i.sstatic.net/NSWgr.png" rel="noreferrer"><img src="https://i.sstatic.net/NSWgr.png" alt="enter image description here"></a></p>
  
Tags: <phylogenetics><hidden-markov-models>
Title: Sequence alignment using Markov Model
ThreadText: # Sequence alignment using Markov Model
  
  (Asked by: username_0 on 2018-09-11)
  
  I am learning about applying Markov model to sequence alignment. The prof says that the transition probabilities from a gap-residue alignment to a residue-gap alignment and vice versa are both 0. Is there any biological/mathematical reason behind this statement? Why are the (X,Y) and (Y,X) cell 0? This is a lecture slide of lecture 1, week 4 of the "Bioinformatics: Introdcution and Methods" course on coursera.
  [![enter image description here](https://i.sstatic.net/NSWgr.png)](https://i.sstatic.net/NSWgr.png)
  
  **Tags:** phylogenetics, hidden-markov-models
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2018-09-11. Score: 6 | Accepted answer
  
  If I understand your question correctly, then I think for case of pairwise alignment, there is a simple explanation.
  
  I believe the key insight is that: *a mismatch should always score better than a gap*.\*
  
  This follows biologically since the insertion/deletion (indel) rate is roughly 1/10th that of the substitution rate (i.e. the occurrence of single nucleotide changes), at least in vertebrates. (This varies across the tree of life but I think the substitution rate virtually always exceeds the indel rate.)
  
  To understand why this matters, consider an example:
  
  ```
  ATG-AG
  ATGT-G
  
  ```
  
  This is an 'impossible alignment' under the probabilities you gave since here we have a transition from a gap-residue alignment to a residue-gap.
  
  However, under our assumption that mismatches are more likely biologically than indels, the correct alignment should be:
  
  ```
  ATGAG
  ATGTG
  
  ```
  
  Indeed, the latter does look like a better alignment.
  
  This also follows for more complex examples, so this:
  
  ```
  ATG--AAG
  ATGTT-AG
  
  ```
  
  Becomes this:
  
  ```
  ATG-AAG
  ATGTTAG
  
  ```
  
  (Or this:
  
  ```
  ATGA-AG
  ATGTTAG
  
  ```
  
  )
  
  \* Strictly, I mean a substitution should score better than an indel (with the associated gap opening and extension penalties). In fact, for the assumption to always be true, a run of mismatches should still score worse than a single indel. This may not always be a correct assumption, consider this example below, is the true alignment case 1) or 2) or something else? Or is in fact a global alignment bad here and this should be split into 2 local alignments? Is there a likely biological mutational event that could explain this? I ask these questions just to point out it is not black-and-white, I don't have clear answers
  
  1)
  
  ```
  CGTACGTAGAGGAATGCCCCCCCCC--------AGCAACGTAGCAT     
  CGTACGTAGAGGAATG---------TTTTTTTTAGCAACGTAGCAT
  
  ```
  
  2)
  
  ```
  CGTACGTAGAGGAATGCCCCCCCCCAGCAACGTAGCAT     
  CGTACGTAGAGGAATGTTTTTTTT-AGCAACGTAGCAT
  
  ```
  
  
  ---
  
  ### Answer by username_1 on 2018-09-12. Score: 1
  
  All Chris\_Rands said is correct: you set the probability of $X\to Y$ and $Y\to X$ to 0 to forbid adjacent insertions/deletions in the alignment. A lot of textbooks including some classical ones use this rule, but in fact, the rule is questionable. It is easier to see this from Smith-Waterman alignment under the affine gap penalty, which is largely the non-probabilistic view of paired HMM.
  
  With the affine gap penalty, a gap of length $k>0$ is scored as
  $$
  g(k)=-(d+k\cdot e)
  $$
  where $d\ge0$ is the gap open penalty and $e>0$ is the gap extension penalty. Suppose we are using a simple scoring matrix where a mismatch gets $-b$, $b>0$. We may see an insertion immediately followed by a deletion (and vice versa) if $b>2e$. It is actually not so difficult for this to happen. For example, for the human-mouse alignment (see the [blastz paper](https://www.ncbi.nlm.nih.gov/pubmed/12529312)), $e=30$ and $b$ is ranged from 31 to 125. It is possible that an $X\to Y$ transition is preferred in the alignment.
  
  Theoretically speaking, it makes more sense to consider immediate transitions between insertions and deletions. In practice, though, the difference between allowing/disallowing such transitions is probably minor most of time.
  
  EDIT: on Chris' example
  
  ```
  CGTACGTAGAGGAATGCCCCCCCCC--------AGCAACGTAGCAT     
  CGTACGTAGAGGAATG---------TTTTTTTTAGCAACGTAGCAT
  
  ```
  
  If we use a scoring matrix with $b>2e$ but disallow adjacent ins-to-del transitions, we will probably end up with an alignment like
  
  ```
  CGTACGTAGAGGAATGCCCCCCCCC-------AGCAACGTAGCAT     
  CGTACGTAGAGGAATG--------TTTTTTTTAGCAACGTAGCAT
  
  ```
  
  This alignment score will be lower.
  
  
  ---
  
  