Details

Autor(en) / Beteiligte

• Comet, J.-P.

Titel

Application of Max-Plus algebra to biological sequence comparisons

Ist Teil von

• Theoretical computer science, 2003-02, Vol.293 (1), p.189-217

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2003

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The classical algorithms to align two biological sequences (Needleman and Wunsch and Smith and Waterman algorithms) can be seen as a sequence of elementary operations in (max,+) algebra: each line (viewed as a vector) of the dynamic programming table of the alignment algorithms can be deduced by a ( max,+) multiplication of the previous line by a matrix. Taking into account the properties of these matrices there are only a finite number of nonproportional vectors. The use of this algebra allows one to imagine a faster equivalent algorithm. One can construct an automaton and afterwards skim through the sequence databank with this automaton in linear time. Unfortunately, the size of the automaton prevents using this approach for comparing global proteins. However, biologists frequently face the problem of comparing one short string against many others sequences. In that case this automaton version of dynamic programming results in a new algorithm which works faster than the classical algorithm.