Propriétés du langage Palingol

Lors d'une recherche sur banque, le programme Palingol gère toute la partie technique consistant à lire les séquences successivement, y choisir un à un les palindromes, etc. Toute cette partie est complètement distincte de la description proprement dite. Créer ou modifier une contrainte se fait au niveau de la description elle-même, et on a la garantie que cette modification n'interfère pas avec le reste du processus.

Possibilités

Palingol permet de décrire une structure :

En particulier :

Palingol ne fait explicitement référence à aucun modèle énergétique, mais on peut parfaitement utiliser des critères de stabilité, soit pour établir la liste initiale de palindromes, soit en tant que contrainte sur les hélices.

Complexité algorithmique

Recherche des palindromes (helix search)

La recherche des palindromes consiste essentiellement à essayer d'apparier deux à deux les bases de la séquence. Un palindrome est une suite de tels appariements. Si on considère une séquence de longueur l, le nombre de couples à examiner varie proportionnellement au carré de l (en fait un peu moins car plus on approche d'une extrémité de la séquence, moins on a de nucléotides candidats ; on néglige cet effet) :

p = O(l 2).

On a rarement besoin de tous les palindromes possibles dans une séquence donnée : en pratique, on peut limiter la recherche à des palindromes dont la taille totale (tête + boucle + queue) est inférieure à t max. On a alors :

p = O(l . tmax).

Le gain peut être apréciable si t max << l, ce qui est généralement le cas.

Examen des contraintes (palingol)

Pour une structure comportant n hélices, on doit considérer les combinaisons de n palindromes parmi p, soit un nombre d'examens :

e = O(p n ) = O(ln . t max n).

On peut considérablement améliorer cette valeur en remarquant que dans une structure connue, on est en général capable de donner une limite supérieure d i à la distance à laquelle on peut placer la ième hélice une fois choisie la (i-1)ème. En effet l'hélice i est alors à choisir parmi p i palindromes avec :

pi = O(di . tmax).

Pour n hélices dont la première est choisie parmi les p palindromes :

e = O(p . Pi=2->n (di . t max)).

En définissant d comme la moyenne géométrique des d i , et en reportant la valeur de p, on obtient :

e = O(l . d n-1. tmaxn).

En tenant compte de la remarque sur les distances (ce qui est réalisé en palingol par la contrainte de type span), on profite donc du fait que d << l. Les deux termes exponentiels de cette formule : d et t max, sont tous deux des propriétés intrinsèques de la structure recherchée. On pourra donc gagner un maximum d'efficacité si on s'approche autant que possible des valeurs minimum imposées par la structure.

Performances

Comme il est de règle avec la programmation descriptive, on obtient un programme d'autant plus performant qu'on place au début les contraines les plus restricitves (celles qui échouent le plus souvent). Comme on ne choisit pas l'ordre dans lequel les hélices sont décrites, c'est sur d'autres éléments qu'on peut intervenir. En particulier, si un motif de structure primaire doit faire partie de la structure, on aura intérêt à l'associer à l'hélice la plus en 5' possible.

Palingol se caractérise par la souplesse d'écriture des descriptions, plus que par la rapidité de la recherche. En effet, la recherche avec un programme écrit en langage Palingol peut être notablement plus longue que la même recherche avec un programme dédié. Par exemple, la recherche d'ARNt est deux fois plus lente qu'avec tRNAScan. Mais si on perd des heures à l'exécution, on a auparavant gagné des semaines de développement du programme... En fait, Palingol doit surtout être utilisé comme un outil de recherche et d'exploration.