Recuperação rápida de subsequências semelhantes em bancos de dados de sequências longas

Embora a distância euclidiana tenha sido a medida de similaridade mais popular em bancos de dados de sequências, técnicas recentes preferem usar funções de distância de alto custo, como a distância de distorção no tempo e a distância de edição, para uma maior aplicabilidade. No entanto, se essas funções de distância forem aplicadas à recuperação de subsequências semelhantes, o número de subsequências a serem inspecionadas durante a busca é quadrático em relação ao comprimento médio L~ das sequências de dados. Propomos um novo esquema de correspondência de subsequências, chamado de correspondência de subsequências alinhadas, onde o número de subsequências a serem comparadas com uma sequência de consulta é reduzido a linear em relação a L~. Também apresentamos uma técnica de indexação para acelerar a correspondência de subsequências alinhadas usando a medida de similaridade da distância de distorção no tempo modificada. Experimentos com sequências de dados sintéticos demonstram a eficácia de nossa abordagem proposta; a nossa superou consistentemente a varredura sequencial e alcançou um aumento de até 6,5 vezes na velocidade.