Le logiciel Lassap (Large Scale Sequence Comparison Package)

Le logiciel Lassap (Large Scale Sequence Comparison Package)

[RE,LO]Lassap [RO,LE]

Lassap est un logiciel qui intègre plusieurs algorithmes de comparaison de séquences, sous une plate-forme commune permettant d'effectuer des recherches à la fois multiples et complexes [94]. Originellement développé à l'INRIA (Institut National de Recherche en Informatique et en Automatique), il est actuellement maintenu et commercialisé par la société Gene-IT[32].

L'importance prise par les projets de Génomique et leurs retombées massives en termes d'information biologique sous forme de séquences suscitent de nombreuses analyses informatiques. Face au volume et à l'hétérogénéité des données de séquences (voir article sur les banques de séquences dans ce même numéro), la pertinence et la valeur heuristique de ces analyses reposent en grande partie sur la possibilité à la fois de les systématiser et de les raffiner par rapport à ce que permettent classiquement les programmes (tels que Blast) qui implémentent essentiellement un seul algorithme. En effet, comparer deux séquences prend différentes significations selon l'algorithme utilisé : par exemple dans un cas, considérant la question comme symétrique, on calculera le meilleur alignement local entre les deux séquences (algorithme de Smith et Waterman), dans un autre, on recherchera la présence d'occurrences de l'une des séquences dans l'autre (algorithme de Boyer-Moore), la première étant alors appelée motif, etc, les nombreux algorithmes disponibles étant autant de variations autour de ce thème de la comparaison deux à deux. Par ailleurs, cette opération binaire de comparaison peut être systématiquement étendue à un ou plusieurs groupes de séquences, conduisant aux recherches de similarités dans des banques de séquences, aux comparaisons de génomes complets les uns avec les autres, ou à l'identification de motifs, parfaits ou dégénérés, dans des ensembles de séquences... (les motifs n'étant eux-mêmes qu'un type particulier de séquences). Enfin, chaque recherche s'inscrit dans un cadre scientifique, et donc méthodologique particulier. Les paramètres de la recherche que sont la ou les banque(s), le système de scores et l'algorithme choisis, sont en général insuffisants pour pleinement spécifier ce cadre. On peut alors vouloir faire appel à des traitements préliminaires visant à sélectionner un sous-ensemble des séquences d'une banque avant de procéder aux comparaisons elle-mêmes, ou à des traitements postérieurs à la comparaison elle-même, ayant pour but de filtrer les résultats. L'hétérogénéité et les limites respectives des programmes implémentant individuellement les différents algorithmes de comparaison de séquences, rendent laborieuse la mise en oeuvre et les modifications d'une démarche un peu plus complexe et précise que la simple comparaison d'une séquence contre une banque avec un seul algorithme. Elle nécessitera souvent, et obligatoirement si l'on veut l'automatiser, l'écriture de programmes annexes, difficilement réutilisables car dépendants des formats de données ou de résultats propres à chaque programme. C'est ce constat qui est à l'origine des motivations sous-jacentes au développement de Lassap [94]. Les solutions apportées par Lassap reposent sur une généralisation des concepts de séquences, banques, algorithmes, etc, et sur une conception modulaire aboutissant à une stricte distinction entre :

les données (banques, paramètres des recherches tels que les matrices de scores, etc), et les traitements préalables aux comparaisons elles-mêmes.
les algorithmes et leurs paramètres propres.
les résultats, leur gestion, leur traitement.
la gestion de requêtes multiples telles que la comparaison d'un ensemble de séquences (qui peut être une banque « personnelle ») contre un autre.

Lassap réunit ainsi plusieurs algorithmes sous une plate-forme commune dont l'organisation et les caractéristiques propres à chaque module permettent la mise en oeuvre de stratégies d'analyse complexes traitant de grands ensembles de données.

Les données sous Lassap

Pour Lassap, toutes les données sont des banques : ainsi, les comparaisons « banque contre banque » sont le cas général, et la démarche classique de comparaison d'une séquence contre une banque devient un cas particulier, celui dans lequel une des deux banques ne contient qu'une séquence. Cette généralisation conduit à traiter une comparaison de séquences de façon complètement symétrique, cette symétrie s'appliquant au format des données, comme aux traitements préalables aux comparaisons elles-mêmes.
Une des limites des possibilités offertes par les programmes classiques est due à la diversité des formats de données qu'il requièrent (en pratique, si l'on veut faire un blast et un fasta sur une même banque, il faut la dupliquer car les deux programmes utilisent des formats différents de cette banque...). Lassap utilise son propre format, reconnu par tous les algorithmes qu'il implémente ainsi que par les programmes effectuant les pré-traitements. Ce format est à la fois humainement lisible et indexé (ce qui permet d'y faire des requêtes efficaces). Le contenu d'une entrée y est séparé en deux parties : la séquence elle-même, et l'en-tête qui contiendra les annotations relatives à la séquence et qui est lui-même divisé en différents champs identifiés par des mots-clefs précis. Lassap inclut des outils permettant de convertir un ensemble de séquences de n'importe quel format « classique » vers le format Lassap, et de manipuler les banques, pour par exemple créer des banques virtuelles, unissant des banques réelles.
À partir des deux banques qui vont être comparées, il est possible d'effectuer des sélections (spécifiquement sur l'une ou l'autre), de façon à restreindre l'ensemble des séquences concernées par la comparaison. Ces sélections peuvent s'effectuer selon différents critères concernant soit la séquence elle-même soit ses annotations. Par exemple, il devient trivial de formuler une requète telle que : « quelles sont les séquences de la division primates d'EMBL contenant le mot liver dans les annotations (voire dans un champ spécifique de celles-ci) qui contiennent avec au plus une erreur un des motifs contenus dans une banque personnelle constituée de sites de fixation de facteurs de transcription expérimentalement mis en évidence comme spécifiques aux tissus hépatiques ». Les différents critères de sélection s'appliquant aux séquences ou aux annotations peuvent aussi être combinés par des opérateurs booléens, permettant de raffiner les sélections.

Les comparaisons elles-mêmes

Plusieurs algorithmes sont proposés, comme les classiques Smith et Waterman, Blast, ou Boyer-Moore. Leur liste complète ainsi que les documentations correspondantes sont disponibles via le serveur WEB de l'Institut Pasteur : [33].
Le traitement des requêtes multiples (séquence contre banque, banque contre banque, etc) est complètement indépendant de l'algorithme particulier choisi (du point de vue de l'analyse effectuée, celui-ci n'est qu'un paramètre du protocole mis en oeuvre ; du point de vue de Lassap, c'est un paramètre de la ligne de commande comme le sont les banques comparées). Elles sont gérées par un module indépendant qui peut utiliser l'existence de plusieurs processeurs pour paralléliser les calculs des différentes comparaisons à effectuer. Toutefois, cette séparation n'est pas visible à l'utilisateur.
Il est possible d'effectuer des sélections au vol ; par exemple, lors d'une comparaison systématique d'un ensemble de séquences contre un autre, n'effectuer la comparaison que si la différence de longueur entre les deux séquences en question n'excède pas x % ...

Traitement des résultats

Habituellement, les programmes de comparaisons de séquences produisent des résultats sous forme de fichiers textes, contenant diverses informations telles que des alignements, scores, etc. Un filtrage des résultats destinés à apparaître dans ce fichier peut être effectué sur différents critères (courramment le score), de même qu'une sélection du type d'informations (avec ou sans alignement par exemple). Ces possibilités sont généralement assez réduites (un filtrage plus fin nécessitera le développement de programmes annexes utilisés a posteriori), et doivent être spécifiées avant que le programme effectuant les comparaisons ne soit exécuté (et donc avant d'avoir connaissance des résultats tels que les scores et le nombre de comparaisons qui atteignent un score donné).

Lassap présente l'originalité de complètement séparer la production et le traitement des résultats :

Les résultats sont produits sous une forme brute et exhaustive mais structurée, et d'un point de vue informatique sous forme de fichiers binaires. L'information pertinente, telle que celle nécessaire à une représentation sous forme d'alignement, y est stockée de manière abstraite et concise. Sous cette forme, ils sont illisibles pour un humain mais se prêtent efficacement à une lecture et des interrogations formulées par des programmes informatiques.
Le traitement des résultats est constitué de sélections effectuées sur divers critères (scores, longueurs des alignements, etc) que l'on peut combiner, et de l'impression dans un fichier texte des informations sélectionnées.

L'existence d'une structure de données intermédiaire entre le calcul des résultats, et leur impression sous forme humainement exploitable offre plusieurs avantages :

Il est possible de la consulter autant de fois qu'on le veut, sans avoir à ré-exécuter le programme effectuant les calculs. Autrement dit, à partir d'un calcul de comparaisons, caractérisé par les données et l'algorithme, on peut générer différentes sorties, simplement en reconsultant la structure contenant les résultats, et en appliquant différents critères de sélections ou différents paramètres d'impression.
Sous cette forme, les résultats eux-mêmes deviennent des données, en ce sens qu'ils peuvent etre utilisés en entrée de programmes de Lassap. En particulier, il peuvent être convertis en banques de format Lassap, et être l'objet eux-mêmes de nouvelles comparaisons.

Utilisation de Lassap

La distribution commercialisée de Lassap est constituée de fichiers exécutables et associés, les sources des programmes n'en faisant pas partie. Elle est installée sur les serveurs centraux de l'Institut Pasteur.

Les étapes de préparation des données, calcul des comparaisons, et traitement des résultats, correspondent à des programmes de Lassap différents, et à des commandes Unix distinctes :

La préparation des banques, conversions en format Lassap, création de banques virtuelles, etc, sont effectuées par les programmes lspbank, lspvbank, lspselect, lspsplit.
La commande lspcalc est celle qui correspond au calcul lui-même et au niveau de laquelle on spécifiera les sélections éventuelles à appliquer avant et pendant le calcul, ainsi que tous les paramètres de la recherche, banques, algorithme, système de scores...
lspextend (calcul d'informations supplémentaires à partir des résultats fournis par lpscalc), lspread (lecture sélective et impression des résultats), lspres (divers traitements sur les résultats, dont notamment la classification de séquences sur la base de leur similarités mesurées par les comparaisons effectuées), lespvres (union de résultats), permettent de mettre en oeuvre différentes stratégies d'analyse des résultats.

En intégrant différents algorithmes de comparaison de séquences, et en considérant distinctement les différentes étapes d'un protocole d'analyse de séquences centré sur des comparaisons multiples, Lassap permet de formaliser ce protocole en langage de commande Unix. Ainsi, il est particulièrement adapté au traitement automatique de nombreuses séquences, qui fait le quotidien des centres de séquençage comme le CNS [34] qui utilise Lassap. D'autres exemples de son utilisation concernent des étapes automatisées de la construction des banques TrEMBL et SwissProt [85], ainsi que Prodom [65].

Outre l'interface ligne de commande Unix, la version Lassap disponible localement à l'Institut Pasteur est enrichie d'interfaces WEB développées par Catherine Letondal [35].

Frédérique Galisson et Nicolas Joly

Édité par :
Service Informatique Scientifique
Institut Pasteur
28 rue du Docteur Roux
75724 Paris CEDEX 15
Tél. : +33 (1) 45 68 85 10
Fax. : +33 (1) 40 61 30 80
Câble : mcb@pasteur.fr Les contributions et suggestions
sont à adresser à :
Laurent Bloch bloch@pasteur.fr
Directeur de la publication :
Philippe Kourilsky
ISSBN : 1244-524 X

Copyright © Institut Pasteur 2000