| Description |
Description
TCS Alignment Toolbox Algebraic Dynamic Programming
This module contains a more general approach to construct
AlignmentAlgorithms by relying on the theoretical concept of Algebraic
Dynamic Programming (ADP) as developed by Giegerich et al.
ADP defines four ingredients for an alignment algorithm:
1.) A signature that defines the permitted alignment operations.
Operations are just function templates with an associated arity, meaning
the number of arguments it takes from the left sequence and from the
right sequence.
In the TCSAlignmentToolbox we have a fixed signature with the following
operations:
REPLACEMENT(1, 1), DELETION(1, 0), INSERTION(0, 1), SKIPDELETION(1, 0)
and SKIPINSERTION(0, 1)
2.) A regular tree grammar that produces alignments, that is: sequences
of operations, in a restricted fashion.
3.) An algebra that can translate such trees to a cost. In the
TCSAlignmentToolbox this is a Comparator.
4.) A choice function, in case of the TCSAlignmentToolbox: the strict
minimum or the soft minimum.
An alignment algorithm in the TCSAlignmentToolbox sense of the word then
is the combination of choice function and grammar. While we provide
hardcoded versions of these combinations in the main package, the adp
package allows you to create your own grammars. You can combine them with
a choice function by instantiating one of the Algorithm classes provided
in this package with a grammar of your choice.
For example:
AlignmentAlgorithm algo = new SoftADPScoreAlgorithm(my_grammar, comparator);
creates an alignment algorithm that implicitly produces all possible
alignments your grammar can construct with the given input, translates them
to a cost using the algebra/comparator you provided and applies the
soft minimum to return the score. This all gets efficient by dynamic
programming.
Note that there is runtime overhead when using this method in comparison
with the hardcoded algorithms. But for complicated grammars this is a much
easier way to go.
For more information on the theory, please refer to my master's thesis:
"Adaptive Affine Sequence Alignment using Algebraic Dynamic Programming"
|
JarCasting