Abstract FR:

Nous présentons une étude des superpositions dans les séquences biologiques dans les trois cas suivants : - superpositions entre plusieurs séquences qui correspondent notamment au cas de l'assemblage de fragments et l'alignement multiples de séquences, ces deux problèmes étant connus comme étant NP-difficiles. - superpositions entre deux séquences qui correspondent aux problèmes des comparaisons de séquences pour lesquelles nous proposons des implantations parallèles aussi bien sur machine SIMD que sur machines MIMD. Nous proposons également une méthode permettant d'améliorer la significativité des scores de comparaison. Cette méthode a été implantée sur une machine parallèle de type MIMD. - superpositions à l'intérieur d'une séquence qui correspondent à la recherche de régularités avec chevauchement : un nouvel algorithme améliorant d'un facteur o (log n) les précédents algorithmes est proposé pour la recherche des facteurs quasipériodiques maximaux et les formes normales gauches et droites permettant une modélisation de ces régularités sont introduites.