A novel optimal multi-pattern matching method with wildcards for DNA sequence

1.Introduction

In recent years, the biological data has significantly increased. DNA sequence is typical biological data that contains basic information of species [1, 2]. DNA sequencing is important in practical areas such as life and agricultural sciences. But nowadays, the DNA sequence data with massive size is a significant computational challenge [3]. Therefore, efficient DNA sequences processing is a major problem to cope with. Pattern matching between different species, i.e., pattern matching for DNA sequence has been a fundamental issue in biomedical engineering, biotechnology and health informatics.

In bioinformatics, DNA sequence alignment is one of the most fundamental and important operation to identify which gene family may contain this sequence. It can be inferred the biological function the sequence may have by DNA sequence alignment. The mechanism of DNA sequence alignment allows the target sequence to be compared with other sequences to find regions of local similarity [1], this process can be modelled as pattern matching problem, in which a pattern is a sequence of DNA characters (A, C, G, T) that is to be searched in a DNA sequence or chromosome [3].

Optimal multi pattern matching for DNA sequence is a challenging issue. For example, when we want to find the locational of biological virus in the genetic sequence, since the virus is not simply copied, some short sequence fragments may be inserted and deleted between two adjacent characters, in this case, pattern matching algorithm with wildcards is necessary [4].

In this paper, we propose a novel algorithm for optimal multiple pattern matching with wildcards for DNA sequence based on a packed string. The algorithm has a pre-processing time complexity of O⁢(|P|) which |P| is the length of pattern P. In cases when the patterns are short enough such that every pattern can be encoded with a single machine word the algorithm runs in O⁢(n+n⁢k) time in worst case, n is the length of main text, and k is the number of pattern strings. The performance of the algorithm can be improved by filtering the patterns according to how many different symbols the pattern is comprised of and the number of characters which occur only once, and the number of wildcard symbols. Special string-matching instructions can also improve the algorithm performance and extend the algorithm to approximate matching algorithm.

The remainder of this paper is organized as follows: Section 2 provides the problem definition and notations. The proposed method is described in Section 3, and then a theoretical analysis of the method is outlined. The experimental results are presented in Section 4. Lastly, conclusions and future works are summarized in Section 5.

2.Definition and notations

The aim of this paper is to find the occurrence of each pattern from set P={P1,…,Pk} in a text T with Pj=pj⁢1⁢pj⁢2⁢…⁢pm⁢jj and T=t0⁢t1⁢…⁢tn such that ti∈∑∪{*} and pkj∈∑∪{*}. The notations are explained as follows:

Let {P1,P2⁢…,Pk} be a set of k patterns, the notations, i.e., m, P, n, T, ∑ and σ are the same as above. A wildcard symbol can match any symbol including itself. The pattern Pj=pj⁢1⁢pj⁢2⁢…⁢pm⁢jj denotes a pattern where every character is saved in a single machine word while Pj′=pj′⁢1⁢pj′⁢2⁢…⁢pm′⁢jj′ denotes the corresponding packed string pattern that several characters are packed into a machine word. T=t1⁢t2⁢…⁢tn denotes a text where every character is saved in a single machine word, and T=t⁢[1]⁢t⁢[2]⁢…⁢t⁢[n] denotes the corresponding packed string text. Multiple characters can be packed into a larger word with a machine word length. The packing process will be given in the following chapter. w denotes the machine word length, t⁢[w] is a sliding window, γ=log⁡σ denotes the number of bits that is enough to store a single character in a single machine word, and α=w/γ denotes the number of characters that can be packed into a single machine word.

3.The proposed methodology

The main idea of the proposed algorithm is to pack each w/log2⁡σ symbols of text and patterns into a single machine word. A single matching word slides along whole text, and in every shifting step, a packed string in a sliding window is compared with a stored packed string of patterns, as shown in Fig. 1. The comparison process includes two sub-processes. The first sub-process is to check if there is a match and the second sub-process is for double checking in order to avoid false matching. The first sub-process is based on shift and “&” called “AND bit-wise operations”, while the second sub-process is based on shift and “|” called “OR bit-wise operations”.

Figure 1.

Slide window on w= 64, γ= 7 and α= 9 packed string of text.

Assume that the machine word w is of a standard size i.e., of either 32 or 64 bits. Then, every machine word can contain up to α=w/log2⁡σ symbols, where σ is the alphabet size. Furthermore, γ=log2⁡σ is the number of bits that is used to encode one symbol from the alphabet. In instance, the first 100 MB of Wikipedia English language (enwik8) has 127 different symbols, i.e., σ= 127, assume w= 64, then γ= 7, α= 9. One machine word can include 9 characters.

The pre-processing phase is first executed to; encode every symbol in text and patterns with a unique integer number and wildcards with 0’s. All the pattern symbols are packed to machine words. Let us assume now that every pattern can be encoded to a single machine word, i.e., m<α, and every comparison process will only take O⁢(1) time. The packaging process is executed by shifting OR bitwise-operations as shown below:

The result is stored as a packed string pattern, p⁢[j], for every pattern that will be used in the comparison process phase.

4.Experimental results

Three data sets were used to test the performance of the proposed algorithm. The first two data sets source from natural language data and the last one sources from a DNA sequence data set. The first nature language data set is from enwik8 (Wiki.) corpus that compromises the first 100 MB of Wikipedia in English language with an alphabet size of 127 different symbols. The second natural language data set is the 4.245 MB King James Version (KJV) of the Bible with an alphabet size of 79 different symbols. The third data set is 96.7 MB hs13.chr file corresponding to the plain ASCII form of the human chromosome 13 (DNA) and the alphabet size is 10 different symbols. Human chromosome 13 is selected because it has moderate size, and it is related to breast cancer, which makes it significant to be analyzed.

The experiments were conducted on a 2.16 GHz Pentium (R) dual 64-bit CPU computer with 2 G RAM and 32-bit Microsoft Windows 8 operating system; we utilized C++ language and Microsoft Visual Studio 2005 to implement the algorithms. We conducted the bench marking of the algorithms in a consistent and controlled environment, and the wildcard character was selected randomly.

The performance of the proposed algorithm was tested against k patterns. Two types of experiments were performed. In these two experiments, a full machine word with 64 bits was used. In the first experiment we used an alphabet size of 256, i.e., γ= 8 bits, and then 8 characters of maximum pattern-length that can deal with the three data sets. The second experiment was only on the DNA data set but in that data set the size of alphabet is 16, i.e., γ= 4 bits. In the implementation of the algorithm, simple and basic bit-wise instructions were used such as OR, AND, shift and complement bit-wise operations. We did not use any complex or special string instructions in order to guarantee that every operation executes in O⁢(1) time. Because the compared algorithms belong to exact matching, they are not approximate matching or based on random algorithms such as genetic algorithm or machine learning algorithms, i.e., the precisions of matching are almost equal, so the main difference on performance is the running time of the algorithms.

Figure 2.

Pre-processing time for the proposed algorithm applied on three data sets.

Figure 3.

Performance of the proposed algorithm on three data sets.

The proposed method ran efficiently in the pre-processing step on the three data sets. Figure 2 shows that for the natural language data set, the pre-processing time was almost identical for both the Wiki and KJV datasets, but it was less for the DNA data set. The figure also shows that the pre-processing time was linear as a function of the number of patterns for all three data sets. In a numerical form, the pre-processing time in sec. for the three data sets, the proposed algorithm can process one hundred thousand of patterns in less than half a second of where every pattern has 8 characters. This means that the algorithm can process almost one million characters in less than half a second.

Figure 4.

Comparison of pre-processing on the DNA data set where γ= 4 and γ= 8 for a big alphabet size data set.

Figure 3 shows that the algorithm performance on the three data sets. From the figure it can be observed that the time complexity for the three data sets is identical and linear. The experimental results shown in Fig. 4 are achieved on the data set that has the smallest alphabet size, i.e., the DNA data set. The dataset is with 10 different symbols from an alphabet where γ= 4 bits can represent all the symbols, and 64 bits can store up to 16 characters. Figure 4 shows the pre-processing time complexity comparison for a big alphabet size data set when γ= 4 and γ= 8. The pre-processing time complexity is the same for the two cases. For the case γ= 8, the algorithm runs more efficiently than when γ= 4, because the number of processed characters in the case of a γ= 4 machine word can save 16 characters (each character needs only one shift and one OR bit-wise operation).

Figure 5.

The time of pre-processing for three algorithms on the Wikipedia data set.

We then compare the performance of the proposed algorithm with the performance of two recent algorithms. The first one is based on the Euclidean distance and the hash function [5] and the second is based on bit-parallelism [6]. Figures 5–7 show the pre-processing time of the three algorithms against the number of patterns for the three data sets. The figures also show that the bit-parallelism based algorithm is less efficient in the pre-processing step than the other two algorithms where the packed string-based algorithm is the most efficient. While the pre-processing time of the packed string-based algorithm is close in pre-processing time with the Euclidean distance and the hash function-based algorithm.

Figure 6.

The time of pre-processing for three algorithms on the KJV data set.

Figure 7.

The time of pre-processing for three algorithms on the data set.

Tables 2–4 show the performance of the algorithms in seconds as a function of the number of patterns on the first 1 MB of the three data sets. As shown in the tables, for the three data sets, the bit-parallelism-based algorithm and the packed string-based algorithm demonstrate a close performance. Of the two, a better performance is observed for the packed string-based algorithm proposed in this paper. Again, it should be stressed that the Euclidean distance and hash function-based algorithm has less efficiency because it uses the Fast Fourier Transform (FFT) which has many interior variables which slows down the algorithm.

5.Conclusions and future works

Pattern matching for DNA sequence has been an essential issue in biomedical engineering and health informatics. The main finding of this article is to propose a faster pattern matching for DNA sequence, i.e., a practical and efficient algorithm for multi-pattern matching with a fixed number of wildcards is proposed. The main idea of the proposed method is to consider matching patterns as packed string patterns with a sliding window. The window slides along the given packed string text, matching against stored packed string patterns. Three data sets are used to test the performance of the proposed algorithm and compare with the state-of-the-art methods. The proposed algorithm was seen to be more efficient than the competitors because its operation is close to machine language (the algorithm operates machine word, so CPU can directly interpret the data), the proposed algorithm is especially effective for the DNA sequence. In future work, the efficiency of algorithms can be improved by merging the proposed bit-parallelism and string packing algorithm with one or more mechanisms such as Euclidean distance and Hash function [7]. In particular, the proposed algorithm can be improved by using specialized word-size packed string-matching instructions. We also plan to improve the work by combining uncertain reasoning models such as evidence theory [8].