Computational mapping of sequences

Computational mapping is a method which allows us to compare sequences even with non-standard evolutionnary events such as shuffles, duplications etc. It can be seen as generalization of the classic alignment of sequences. The approach is pairwise and asymetric: mapping a sequence s over a sequence t consists in finding the best way of splitting s into a fixed (or not) number of parts in order to maximize the sum of the alignment scores of all parts against the whole sequence t. This best way is easily determined by dynamic programming.

It can be used to compare DNA, proteins and even genomes (for instance by identifying a genome with the sequence of its genes). The approach and the algorithm are presented in this article published in the online open acces revue Algorithm for Molecular Biology. Here is a text dealing more specifically with genomes comparison written for the ASMDA 2007 conference.

The C sources of the softwares computing and displaying the maps are freely available by this link. Please contact me at didier(at)iml.univ-mrs.fr if you have any question, remark or suggestion.