[Seqan-dev] Replacing the alignment algorithms.

[Rahn, René <rene.maerker@fu-berlin.de>]

Dear all, 

we have made substantial modifications to the alignment algorithms. The entire alignment module was refactored concerning the algorithms so with the current trunk version you will use the new implementation which facilitates a unification of all standard dp algorithms.

For a detailed list of changes you can review the white paper on http://trac.seqan.de/wiki/WhitePapers/AlignmentAlgorithmsStructure.

There you find a description of the general concept of the new alignment algorithms and where you can find the source code regarding the new implementation.

The global alignment interfaces haven't changed, so that most of you should have no problems using the new core. We also still support the old algorithms but they are not included in the align.h header file anymore. You have to include them explicitly in order to get access to the old implementations. Note that in the early year of 2013 we will remove them completely from our trunk. The Waterman-Eggert implementation is yet not affected by the change but the migration of this algorithm will come soon.
Note that for the specialized alignment algorithms Meyers-Bitvector, Hirschberg and Meyers-Hirschberg, will be not affected by the remodelling.

There are some changes that might affect your algorithms:

  1. Now all dp algorithms use the same traceback function: All InDels are left-aligned. And a gap in the horizontal sequence is preferred over a gap in the vertical sequence if multiple alignments are possible. This is different to the behavior of the old Needleman-Wunsch and the Smith-Waterman algorithm but the same as with the Gotoh implementation.

  2. The global score interfaces  have been modified. Please, review the white paper http://trac.seqan.de/wiki/WhitePapers/AlignmentAlgorithmsStructure to get more details. (information regarding the score will be updated soon)

  3. Now we also support Fragments for the local alignment. 

  4. You can determine the gap cost function by specifying the costs for gap open and gap extend of the Score object.

  5. We do not support all bands anymore. That is for the standard global alignment the band has to cover both the sink and the origin of the alignment matrix. If this is not given no alignment will be computed and minus infinity (MinValue<TScoreValue>::VALUE, where TScoreValue is the value type for the Score object), will be reported. In order to compute bands where both, the lower and the upper diagonal of the band, cross the same row, and accordingly column, the respective initial- or/and end-gaps have to be free. 

We support most of the old behavior hoping this makes the migration less laborious. Nonetheless, don't hesitate to contact me if something is broken in your implementation so we can figure out what happened and how to fix it.

I wish you all a merry Christmas and a happy New Year!!!

Kind regards,

René Rahn

---

René Rahn

Ph.D. Student

------------------------------------------------

rene.rahn@fu-berlin.de

+49 (0)30 838 75 277

------------------------------------------------

Algorithmic Bioinformatics (ABI)

Department of Informatics 

Room  018

------------------------------------------------

Freie Universität Berlin

Takustraße 9 

14195 Berlin

------------------------------------------------