Fast practical online exact single and multiple pattern matching algorithms in highly similar sequences. (23rd April 2019)

• Record Type: Journal Article
• Authors: Nsira, Nadia Ben; Lecroq, Thierry; Prieur-Gaston, Élise
• Is Part Of: International journal of data mining and bioinformatics. Volume 22:Number 1(2019)
• Page Start: 1
• Page End: 18
• Publication Date: 2019-04-23
• Subjects: computational biology -- bioinformatics -- algorithm design -- pattern matching -- string matching -- DNA sequences -- genomic sequences -- Landau-Vishkin algorithm -- Aho-Corasick algorithm -- similar sequences; Data mining -- Periodicals; Bioinformatics -- Periodicals; 006.312
• Languages: English
• ISSNs: 1748-5673

Abstract

With the advent of high-throughput sequencing technologies there are more and more genomic sequences of individuals of the same species available. These sequences only differ by a very small amount of variations. There is thus a strong need for efficient algorithms for performing fast pattern matching in such specific sets of sequences. In this paper, we propose efficient practical algorithms that solve on-line exact pattern matching problem in a set of highly similar DNA sequences. We first present a method for exact single pattern matching when k variations are allowed in a window which size is equal to the pattern length. We then propose an algorithm for exact multiple pattern matching when only one variation is allowed in a window which size is equal to the length of the longest pattern. Experimental results show that our algorithms, though not optimal in the worst case, have good performances in practice.