Récupération rapide de sous-séquences similaires dans des bases de données de longues séquences

Bien que la distance euclidienne ait été la mesure de similarité la plus populaire dans les bases de données de séquences, les techniques récentes préfèrent utiliser des fonctions de distance à coût élevé telles que la distance par déformation temporelle et la distance d'édition pour une applicabilité plus large. Cependant, si ces fonctions de distance sont appliquées à la récupération de sous-séquences similaires, le nombre de sous-séquences à inspecter pendant la recherche est quadratique par rapport à la longueur moyenne L~ des séquences de données. Nous proposons un nouveau schéma d'appariement de sous-séquences, appelé appariement de sous-séquences alignées, où le nombre de sous-séquences à comparer avec une séquence de requête est réduit à une fonction linéaire de L~. Nous présentons également une technique d'indexation pour accélérer l'appariement de sous-séquences alignées en utilisant la mesure de similarité de la distance modifiée par déformation temporelle. Des expériences sur des séquences de données synthétiques démontrent l'efficacité de notre approche proposée ; la nôtre a constamment surpassé le balayage séquentiel et a atteint un accélération allant jusqu'à 6,5 fois.