Vector Algorithms for Approximate String Matching
© World Scientific Publishing Company



Anne Bergeron et Sylvie Hamel



Résumé :


     Les algorithmes vectoriels nous permettent de calculer, à partir d'un vecteur d'entrée e, un vecteur de sortie r, en un nombre borné d'opérations, indépendant de m, la longueur des vecteurs. Les opérations permises sont souvent limitées aux opérations logiques sur les bits, disponibles dans les processeurs, incluant les "shifts" et l'addition binaire avec retenue. Ces restrictions impliquent que l'existence d'un algorithme vectoriel pour un problème particulier donne lieu à des implémentations très efficaces.

     Cet article présente des résultats généraux sur l'existence et la construction d'algorithmes vectoriels, notre attention étant principalement centrée sur des problèmes reliés à la bioinformatique. Nous montrons qu'il existe des algorithmes vectoriels efficaces pour le problème de l'alignement approximatif de chaînes de caractères avec distances arbitraires, généralisant un résultat de E. Myers. Nous donnons aussi une caractérisation d'une classe d'automates pour laquelle il est possible de construire automatiquement un algorithme vectoriel à partir de la table de transition de l'automate.