Calimul homepage


Calimul: Comparaison d'Alignements multiples


Explication succinte de la méthode

Score des alignements & somme des paires

Le score d'un alignement multiple doit rendre compte de la qualité de l'alignement. Les algorithmes utilisés cherchent à maximiser ce score, qui est une indication de l'alignement optimal. Quelle que soit la méthode d'alignement multiple, le problème de la méthode de calcul du score se pose. La plus utilisée est le score somme des paires (SP) " sum of pairs " : somme sur chaque colonne de tous les scores entre acides aminés pris deux à deux (selon une matrice de substitution). En faisant la moyenne par paires ou la somme sur l'ensemble des colonnes, on obtient un score pour l'alignement.


Ce que fait Calimul

Face aux nombreux algorithmes d'alignements multiples disponibles, possédant chacun ses propres avantages et inconvénients, et son propre calcul de score, il faut pouvoir juger quel est le meilleur, ou plutôt, le plus adapté à son problème.

Calimul est un outil de comparaison d'alignements multiples, qui se base aussi sur la somme des scores des paires des acides aminés par colonne, mais qui permet à l'utilisateur de fixer des paramètres qui lui semblent pertinents pour l'évaluation d'un alignement multiple (notamment en ce qui concerne les gaps).

On peut soumettre à Calimul différents alignements d'un même ensemble de séquences obtenus avec plusieurs algorithmes, et il fournira un score pour chaque alignement - indépendant de l'algorithme utilisé pour construire l'alignement, mais calculé de la même manière sur chacun des alignements. Ce score est normalisé entre 0 et 1.

Les paramètres importants dans l'évaluation du score d'un alignement sont les différentes pénalités fixées pour les gaps.

Traitement des gaps

La prise en compte des gaps est un point critique du calcul de score. Nous avons choisi de distinguer les différentes positions d'un gap et de permettre à l'utilisateur de modifier les valeurs de pénalité définies par défaut.

On discernera ici les différentes positions d'un gap par des lettres (O pour ouverture, E pour extension et F pour fermeture) ainsi que les pénalités de gaps face à un acide aminé (AA). La pénalité d'un gap contre un acide aminé, (O,AA), (E,AA) ou (F,AA), est indépendant de ce dernier. Par défaut, les pénalités, modifiables par l'utilisateur, sont définies par rapport à la valeur minimale de la matrice de substitution choisie :


Pondération des séquences dans l'alignement

Le calcul du score se base sur la somme du score des paires par colonne, en considérant les colonnes comme indépendantes. Dans le cas de figure où l'alignement soumis contient plusieurs séquences très similaires face à une ou plusieurs séquences plus éloignées, il est apparu intéressant de pondérer les séquences selon leur similarité. En effet, on sait que ce ne sont pas les séquences très similaires qui posent problème dans les alignements. Elles seront bien alignées quelle que soit l'algorithme. Néanmoins, cette information redondante peut jouer sur l'alignement obtenu en donnant trop de poids à des séquences sur-représentées. Dans le programme, on peut donc choisir de compter moins les séquences très similaires (option pondération).


Pour plus d'information, lire le rapport sur Calimul

Ecrit par Sandrine Perrin - 2010