Sequence problems belong to the most challenging interdisciplinary topics
of the actuality. They are ubiquitous in science and daily life and occur, for
example, in form of DNA sequences encoding all information of an
organism, as a text (natural or formal) or in form of a computer program.
Therefore, sequence problems occur in many variations in computational
biology (drug development), coding theory, data compression, quantitative
and computational linguistics (e.g. machine translation).
In recent years appeared some proposals to formulate sequence
problems like the closest string problem (CSP) and the farthest string
problem (FSP) as an Integer Linear Programming Problem (ILPP). In the
present talk we present a general novel approach to reduce the size of the
ILPP by grouping isomorphous columns of the string matrix together. The
approach is of practical use, since the solution of sequence problems is very
time consuming, in particular when the sequences are long.
Buscar en Dimension