# Sequence alignment using Markov Model

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


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