To be able to calculate the probability of a certain alignment between S 1 and S 2 , we need to devise a model for the evolution of a sequence. We will be working with a simple 3-state HMM indel model, using a more complex nucleotide substitution model, given by an emission matrix E, for the emission probabilities. We wish to investigate region-specific selectional behaviour along the genome of S 1 . We may thus apply a partition P to our sequence S 1 , given by a sequence of partition points {p 0 , p 1 , ..., p |P| }, where clearly p 0 = 0 and p |P| = |S 1 |. Because we are interested in certain global features, we may wish to group particular partition segments together into regions of a Sequence Annotation Figure 5 Sequence Annotation. An example of our input data and annotation. We see here the 'ancestral' sequence S 1 , whose genes structure G is given by coding regions in two reading frames GRF1 and GRF2. We apply a partition P to the sequence, where a breakpoint occurs whenever there is a change in gene structure. We annotate this partition with R = 3 different types of region for non-, single and double-coding respectively. Finally we have the descendent sequence S 2 .