ProbA

ProbA (Mückstein et al., 2002) enables global pairwise alignment using the partition function over all canonical alignments to calculate the probability of every match between a position in the first and a position in the second sequence. For the calculation of the partition function we used a modified alignment algorithm that avoids the generation of solutions that are represented differently but are equivalent from a semantic point of view. Furthermore we include a parameter governing the relative weight of alignment paths with different scores (Kschischo 2000) and extend previous approaches to stochastic pairwise alignments by a stochastic backtracking procedure that can be used to obtain ensembles of suboptimal alignments with correct statistical weights.