Alignment with Context Dependent Scoring Function

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.