In the paper by Gambin et al. (2002) we introduced the model of contextual alignment of
biological sequences. It is an extension of the classical alignment, in which the cost of a
substitution depends on the surrounding symbols. Consequently, in this model the cost of
transforming one sequence into another depends on the order of editing operations. In this
paper, we strengthen some of our results which concern reconstructing (the representation
of) all the orders of operations which yield this optimal cost. We also present a procedure
to construct context-dependent substitution tables and discuss the distribution of scores of
local contextual alignment, which is shown to follow the extreme value distribution in the
gap-free, reduced context case. We also demonstrate a linear time algorithm to compute the
optimal local and global alignment without gaps.
