Le langage Palingol

Pour plus d'informations, on poura consulter le Palingol user's guide.

Description d'une structure

La description d'un motif structural correspond à l'ennoncé d'une liste de propriétés que doit posséder un objet pour être considéré comme une occurence du motif. En d'autres termes, une description est un ensemble de contraintes.

Un motif structural est formé par les interactions intramoléculaires entre bases, qui forment des hélices plus ou moins longues. Une structure peut donc être caractérisée par :

Toutes les contraintes doivent être remplies pour pouvoir considérer que la structure a été identifiée.

Techniquement, chaque contrainte s'exprime sous forme d'une expression booléenne, par exemple :

   l'hélice comporte au moins 6 bases

et une description est une expression booléenne composée de sous-expressions, comme :

   l'hélice comporte au moins 6 bases
et la boucle comporte exactement 4 bases
et (   la deuxième base de la boucle est un U
    ou la dernière base de l'hélice est un A )
et il y a au moins deux G dans l'hélice.

Une occurence est trouvée quand une telle expression prend la valeur VRAI.

Le langage Palingol est donc un langage déclaratif. Il permet d'exprimer formellement le type de contraintes nécessaires à la description d'un motif structural.

Descripteurs

Une hélice est composée de trois éléments :

Pour chacun de ces éléments, on considère quatre paramètres :

Un descripteur est composé de l'association d'un paramètre et d'un élément. Ainsi :

Note. Ces paramètres sont redondants : on pourrait calculer la position de fin d'un élément en connaissant sa longueur et son début, ou sa longueur à partir de sa séquence. De plus, les tailles de la tête et de la queue sont égales (on ne considère pas les bulges dissymétriques). Mais la présence de plusieurs paramètres permet d'écrire un code plus clair, et limite les risques d'erreur.

Opérateurs

Seuls quelques opérateurs de chaque type sont donnés à titre d'exemple.

On peut combiner entre eux les descripteurs avec les opérateurs classiques (tous les opérateurs sont préfixés) :

calcul : addition (add), soustraction (sub), multiplication (mul), division (div).

chaînes : sous-chaîne (sstr), concaténation (strcat).

Une contrainte est représentée par une expression booléenne, simple ou composée :

comparaison : égal (eq), inférieur (lt), supérieur (gt), inférieur ou égal (le), supérieur ou égal (ge).

opérateurs booléens : non (not), et (and), ou (or).

motifs : motif exact (strstr), avec erreurs (patsearch) ou par matrice de score (scoremat).

Les instructions qui n'expriment pas une contrainte

Certaines instructions peuvent servir à autre chose qu'à exprimer une contrainte structurale. Une telle instruction est cependant considérée comme une expression booléenne, mais elle renvoie toujours "vrai" après exécution. On dit qu'une telle instruction est "à effet de bord".

impression : imprimer (print).

"and" implicite et pruning

Une description en Palingol est en définitive une grande expression booléenne. Puisqu'on cherche une structure qui satisfasse toutes les contraintes, cette grande expression est un and entre toutes les expressions décrivant les contraintes unitaires. Pour alléger l'écriture, Palingol considère que deux expressions consécutives sont implicitement reliées par un opérateur and.

Puisqu'un programme Palingol est une expression "and" composée, il suffit qu'une des sous-expressions soit fausse pour que toute l'expression soit fausse également. Dans ce cas, il est inutile de continuer à évaluer les sous-expressions suivantes. Palingol utilise ce mécanisme (dit "pruning") pour accélérer la recherche d'un motif, mais il a une autre implication importante : si on place les instructions d'impression à la fin de la description, elles ne seront "évaluées" (elles renvoient toujours "vrai") que si tout ce qui précède a été trouvé vrai. Ainsi, on n'imprime que lorsqu'on a effectivement trouvé une occurence de la structure.

Structure d'une description

Une description complète se compose de deux sortes de contraintes : les contraintes portant sur chaque hélice individuelle, et les contraintes portant sur les relations entre les différentes hélices. Ces contraintes sont exprimées en Palingol dans des sections identifiées par un en-tête particulier:

helix : chaque hélice est décrite dans une section helix. Il y a donc autant de sections helix que d'hélices dans la structure. Les sections helix apparaissent dans un ordre précis, qui est celui des start head.

cross : les relations inter-hélices sont décrites dans la section cross. Il y a une section cross par description, et elle vient après toutes les sections helix. A l'intérieur de la section cross, les contraintes sont exprimées comme décrit plus haut, mais chaque élément d'une hélice est suivi de son numéro (précédé du signe #):

( ge ( length loop #1 ) ( length head #2 ) )
signifie que la boucle de la première hélice doit être au moins aussi longue que la tête de la deuxième.

span : pour des raisons d'efficacité, une des contraintes possibles entre hélices est décrite séparément : la distance maximum entre deux hélices successives. Pour ce faire, une section span apparaît entre la derniere section helix et la section cross. Pour une structure à h hélices, la section span contient h-1 descripteurs, chacun suivi d'un nombre ; le ième nombre indique la distance maximum entre le début de la tête de la (i+1)ième hélice et le descripteur indiqué pour la ième hélice. Par exemple:

span { start tail 8 end tail 20 start loop 10 }
est la section span d'une structure à 4 hélices. La tête de la deuxième hélice doit commencer au maximum 8 bases après le début de la queue (start tail) de la première.

Une description a donc la forme générale suivante :

helix {
contraintes sur l'hélice #1
}
helix {
contraintes sur l'hélice #2
}
...
span { descripteur valeur ... }
cross {
contraintes sur les relations entre hélices
}

Exemple

Pour cet exemple, on suppose qu'on recherche un motif en forme de pseudo-noeud, avec un certain nombre de caractéristiques connues.

Selon la nomenclature des pseudo-noeuds (à gauche), on appelle respectivement L1 et L2 les deux zones non appariées à l'intérieur du pseudo-noeud. Pour Palingol (à droite), chaque hélice a sa boucle, qui comprend tous les nucléotides situés entre la tête et la queue, même ceux qui sont impliqués dans la formation d'une autre hélice.

Voici comment se présenterait un programme Palingol pour le motif recherché (les lignes en italiques commençant par # sont des commentaires, qui ne sont pas interprétés) :

# Hélice 1
helix {

  # L'hélice a au moins 4 bases
  ( ge ( length head ) 4 )

  # La boucle a au moins 7 bases
  ( ge ( length loop ) 7 )
}

# Hélice 2
helix {

  # L'hélice a au moins 3 bases
  ( ge ( length head ) 3 )

  # L'hélice a au plus 9 bases
  ( le ( length head ) 9 )

  # La boucle a au moins 8 bases
  ( ge ( length loop ) 8 )
}

# distance maximum entre les hélices
span

  # max. 9 bases de la fin de la tête #1 au début de la tête #2
  { end head 9 }

# contraintes croisées
cross {

  # Les hélices sont séparées d'au moins 3 bases (L1)
  ( ge ( start head #2 ) ( add ( end head #1 ) 3 ) )

  # Disposition des hélices en pseudo-noeud
  ( lt ( end head #2 ) ( start tail #1 ) )

  # Les hélices sont séparées d'au moins 2 bases (L2)
  ( ge ( start tail #2 ) ( add ( end tail #1 ) 2 ) )

  # On imprime le résultat
   ( print "Motif en position %d\n" ( start head ) )
}

Des structures ci-dessous, seule la troisième est un exemple du motif (pour les deux premières, la contrainte qui fait échouer la recherche est reportée en dessous) :