# FACC: A Novel Finite Automaton Based on Cloud Computing for the Multiple Longest Common Subsequences Search

Authors: Yanni Li; Yuping Wang; Liang Bao
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Searching for the multiple longest common subsequences (MLCS) has significant applications in the areas of bioinformatics, information processing, and data mining, and so forth, Although a few parallel MLCS algorithms have been proposed, the efficiency and effectiveness of the algorithms are not satisfactory with the increasing complexity and size of biologic data. To overcome the shortcomings of the existing MLCS algorithms, and considering that MapReduce parallel framework of cloud computing being a promising technology for cost-effective high performance parallel computing, a novel finite automaton (FA) based on cloud computing called FACC is proposed under MapReduce parallel framework, so as to exploit a more efficient and effective general parallel MLCS algorithm. FACC adopts the ideas of matched pairs and finite automaton by preprocessing sequences, constructing successor tables, and common subsequences finite automaton to search for MLCS. Simulation experiments on a set of benchmarks from both real DNA and amino acid sequences have been conducted and the results show that the proposed FACC algorithm outperforms the current leading parallel MLCS algorithm FAST-MLCS.


---

## Body

## 1. Introduction

Searching for MLCS is a classic dynamic programming problem. LetΣ be a set of the finite or infinite alphabet, and X=x1,x2,…,xm be a finite sequence of symbols drawn from Σ, that is, xi∈Σ, i=1~m. A sequence Z=z1,z2,…,zk is called a subsequence of X if it satisfies zj=xij, j=1~k and 1≤i1<i2<⋯<ik≤m, that is, Z=xi1,xi2,…,xik. For two given sequences X and Y, Z is called a common subsequence (CS) of X and Y if and only if Z is simultaneously a subsequence of both X and Y. When no other common subsequence is longer than Z, Z is named the longest common subsequence (LCS) of X and Y. Similarly, given a set of sequences {S1,S2,…,Sk} drawn from Σ, a subsequence is called their multiple longest common subsequence (MLCS) if it is a subsequence for all of them (this subsequence is called a common subsequence), and no other common subsequence is longer than it.Searching for the MLCS is significant for a number of applications in the areas of bioinformatics, information processing, data mining, and pattern recognition [1] and so forth. In the above-mentioned application areas, information can be usually represented as a sequence over a finite or infinite alphabet. For instance, a protein can be expressed as a sequence of twenty different symbols (amino acid) in biology, and a DNA sequence can be described as a sequence of four symbols A, C, G, and T [2]. A program source code can be represented as a sequence over alphabets, that is, ASCII or Unicode. In a specific domain, similarly, web information can be regarded as a word sequence of the domain-ontology. We can explore and discover valuable information by making a comparison and analysis of the sequences. For example, in the biological field, sequence comparison has been successfully used to establish a link between cancer-causing genes and normal genes. By finding the similarity between gene sequences, we can obtain valuable information on genetic diseases [3–5], too. In web information search and data mining, by determining the MLCS of word sequences of the domain-ontology, we can not only increase the accuracy rate of information retrieval, but also mine considerably valuable information. In the programming analysis, by discovering the MLCS among program source codes, we can acquire their redundancy and similarity and eliminate the redundancy or detect clone codes.Searching for the LCS of two or more given sequences is a classic NP-hard problem [6]. Wagner and Fischer [7] first introduced a classic dynamic programming algorithm (DP) for solving the LCS problem of two sequences, and both its time and space complexity are O(mn), where m and n are the lengths of the two sequences, respectively (the same notations are used in what follows). However, its main drawbacks are as follows: it has a higher time and space complexity, and it can only find the LCS of two relatively short sequences, but can hardly deal efficiently with the LCS problem of the two longer sequences. Hirschberg [8] presented a new LCS algorithm based on the idea of the “divide and conquer” approach, which reduces space complexity to O(m+n) and gives a better solution to the problem of the longer sequences. Using a decision tree model, Ullman et al. [9] (1976) devised a better LCS algorithm with lower bound O(mn) of the time complexity. Based on the effective detection of all the major matched points between compared sequences, Hunt and Szymansi [10] designed a new LCS algorithm with the time complexity of O(nloglogn), where n is the maximum length of the compared sequences. The algorithm was later simplified by Bespamyatnikh and Segal [11]. Masek and Paterson [12] put forward an improved dynamic programming algorithm by using a fast algorithm to compute the sequence editing distance, which reduces the time complexity to O(n2/logn).To further improve the time complexity of LCS algorithms, researchers have begun to study the parallel LCS algorithm. Based on a CREW-PRAM model, Aggarwal and Park [13] and Apostolico et al. [14] proposed parallel LCS algorithms with the time complexity of O(logmlogn) by using mn/logm processors, respectively. Freschi and Bogliolo [15] presented another new parallel LCS algorithm by using some packed arrays and m+n processors based on the run-length-encoded (RLE) string. The time complexity of the algorithm is O(m′n+mn′-m′n′), where m′ and n′ are the numbers of runs in their RLE representation, respectively. Liu and Chen [16] presented a specific parallel MLCS algorithm over alphabet {A, C, G, T}, FAST-LCS, based on proposed pruning rules which is more efficient than the previous works. The space and time complexity of the algorithm are max{4*(n+1)+4*(m+1),L} and O(|LCS(X,Y)|), respectively, where L is the number of identical character pairs and |LCS(X,Y)| is the length of the LCS of X and Y. Wang et al. [17–19] developed the efficient MLCS algorithms parMLCS and Quick-DP, respectively, based on dominant points approach, which have reached a near-liner speedup for large number of sequences. It is worth mentioning that Yang et al. [20], as a new attempt, develop an efficient parallel algorithm on GPUs for the LCS problem. But regretfully, the algorithm is not suitable for the general MLCS problem.To meet the needs of practical applications, some researchers have also studied some variations of the LCS problems, such as the longest common increasing subsequence (LCIS) problems, the longest increasing subsequence (LIS) problems, and the common increasing subsequence (CIS) problems, and so forth. Fredman [21] proposed an algorithm for LIS problems. The optimal time complexity of the algorithm is O(nlogn) when the average length of sequences equals n. By combining LCS with LIS, Yang et al. [22] defined a common increasing subsequence (CIS) and designed a dynamic programming algorithm for two sequences CIS problems. The space complexity of the algorithm is O(mn). Brodal et al. [23] present an algorithm for finding a LCIS of two or more input sequences. For two sequences of lengths m and n, where m≥n, the time complexity and space complexity of the algorithm are O((m+nl)loglogσ+Sort) and O(m), respectively, where l is the length of an LCIS, σ is the size of the alphabet, and Sortis the time to sort each input sequence.Nevertheless, the aforementioned algorithms have the following disadvantages: (1) most of them are inapplicable to the problems with more than two sequences (especially a considerable number of sequences, a large alphabet, and a long average length of the sequences); (2) the efficiency and effectiveness of a few parallel algorithms remain to be improved; (3) the parallel implementations of the algorithms are of a certain difficulty due to their complicated concurrency, synchronization, and mutual exclusion, that is, none of the existing algorithms employed simple and cost-effective high performance parallel computing framework such as MapReduce for implementing their algorithms; (4) most of the algorithms did not provide an abstract and formal description to reveal the inherent properties of the MLCS problem. To overcome these shortcomings, a novel finite automaton based on cloud computing for the MLCS problem was proposed in this paper. The main contributions of this paper are as follows.(1)
All common subsequences (CS) of then sequences are abstracted as the language over their common alphabet Σ, that is, every CS of n sequences is a sequence over the Σ.(2)
Based on the ideas of the matched pair and finite automaton, a novel finite automaton which can recognize/accept all of the CSs ofn sequences is presented.(3)
A formal definition of the finite automaton was introduced, and its properties were verified.(4)
A novel parallel algorithm FACC was proposed. FACC is by abstracting the MLCS problem as one of searching for the longest path on the finite automaton, and was implemented based on the new parallel framework MapReduce of cloud computing and a variety of optimization techniques.(5)
A quantitative analysis of the time and space complexity of the FACC was conducted.(6)
The algorithm FACC was validated on the DNA and amino acid sample sequences from ncbi and dip databases. Then, the comparison of the time performance between FACC and the leading algorithm: FAST-LCS [16] was made. The experimental results show that the proposed FACC outperforms FAST-LCS.The rest of this paper is organized as follows. Section2 introduces some notations and concepts in this paper for convenience discussion. Section 3 presents the finite automaton Atm for recognizing common subsequence and its basic properties. Section 4 proposes a new algorithm called finite automaton based on cloud computing (FACC) and describes its implementation in detail. Section 5 explains the analysis of the time and space complexity of FACC. The experiments are made and the analysis results are explained in Section 6. Finally, Section 7 concludes the research.


## 2. Notations and Basic Concepts

For convenience, the following notations are adopted in Table1.Table 1
Notations and their meanings.
Notations
Meaning
Σ
The common alphabet ofN sequences
Σ
i
The set of alphabets in theith sequence
S
k
(
k
=
1,2
,
…
,
d
)
Thekth sequence, with d being the number of sequences drawn from Σ
T
A set of sequences drawn fromΣ
P
=
[
p
1
,
p
2
,
…
,
p
d
]
A matched pair
Q
=
{
Q
0
,
Q
1
,
…
,
Q
n
}
The set of the FA states
δ
The FA’s transition function
Q
0
=
(
0,0
,
…
,
0
)
The FA’s initial state
F
The set of the FA’s final states
Atm
The FA recognizing/accepting all of the CSs of sequences fromT
Σ
*
Kleene closure ofΣ, Σ*  ={x∣x is a sequence from Σ with the length of zero or nonzero}
L(Atm)
A language recognized/accepted by the AtmNote that a sequence over some alphabet is a finite sequence of symbols drawn from that alphabet. According to the formal language and automaton theory, we can view the common subsequences of all sequences on setT as a language L of the common alphabet Σ, and then regard the MLCS of the over sequences as the one or several longest statements of the language L. Based on this idea, a novel finite automaton Atm which can recognize/accept the L is designed, and the Atm for MLCS was constructed quickly based on a new constructing-searching algorithm and the MapReduce parallel framework of cloud computing proposed in this paper, meanwhile the MLCS can be easily achieved.For easy understanding, some basic concepts in the following are introduced, and the properties of theAtm are discussed.Definition 2.1.
SupposeSk∈T is a sequence over Σ for k=1~d. Let Sk[pk]∈Σ denotes the pkth (pk=1,2,…,|Sk|) character in sequence Sk. For the sequences S1,S2,…,Sd from T, vector p=[p1,p2,…,pd] is called a matched pair of the sequences, if and only if S1[p1]=S2[p2]=⋯=Si[pi]=⋯=Sd[pd]=ch (i=1,2,…,d,ch∈Σ), where ch is the character corresponding to the matched pair p, denoted as ch(p).For example, for two sequencesS1=abcfg and S2=bacgf, one can get the following matched pairs by Definition 2.1: [1,2], [3,3], [4,5], [2,1], and [5,4] with their corresponding ch’s being a, c, f, b, and g, respectively.Definition 2.2.
For the sequencesS1,S2,…,Sd from T, p=[p1,p2,…,pd] and q=[q1,q2,…,qd] are two matched pairs. one calls p=q if and only if pi=qi for i=1,2,…,d. If p≠q and qi<pi for i=1,2,…,d, one calls p a successive matched pair of q, and denote it as q<p. If q<p and there does not exist a matched pair r=[r1,r2,…,rd] for S1,S2,…,Sd such that q<r<p, one calls p a direct successor matched pair of q, denoted as q→p.Definition 2.3.
For the sequencesS1,S2,…,Sd, from T, let q=[q1,q2,…,qd] be a matched pair. If there does not exist a matched pair p=[p1,p2,…,pd]  (p≠q) such that p<q, one terms q an initial matched pair. In general, there may be more than one initial matched pair from T.Taking above sequencesS1 and S2 as an example, we can see that the matched pairs [3,3], [4,5], and [5,4] are the successive matched pairs of matched pairs [1,2] and [2,1]. Moreover, the matched pair [3,3] is a direct successive matched pair of the matched pairs [1,2] and [2,1], wherein [1,2] and [2,1] are two initial matched pairs in total for sequences S1 and S2.Based on above the definitions, the following conclusion can be easily inferred.Lemma 2.4.
The total number of all possible initial matched pairs is less than or equal to|Σ| regardless of |T|.


## 3. Finite AutomatonAtm for Recognizing Common Subsequence and Its Basic Properties

It can be seen from the above discussion that the characters in the MLCS fromT must be the characters corresponding to their matched pairs. In the following, based on some ideas and concepts from finite automaton (Atm), we can see the matched pairs of T as states of the Atm and construct the Atm which can recognize/accept all the CSs of T by defining a specific transition function. The formal definition of the Atm is as follows.Definition 3.1.
The common subsequence finite automatonAtm is a 5-tuple, that is,(3.1)Atm={Q,Σ,δ,Q0,F},
where Q—Q={Q0,Q1,…,Qn} is a finite set of states of the Atm, where Qi is the state corresponding to the ith matched pair of T for i=0~n; Σ—the common alphabet of sequences set T; δ—the transition function δ:Q×Σ→Q. For for all a∈Σ and Qi, one defines the transition function δ as follows：(3.2)δ(Qi,a)={Qj,ifQi⟶Qj,ch(Qj)=aϕ,else.
Q
0—Let Q0=(0,0,…,0), the initial state of the Atm. F—The set of final states of the Atm, that is, F={Qi∣ifδ(Qi,a)=Φ∀a∈Σ}.It can be seen from Definition3.1 that the Atm is a deterministic finite automaton (DFA), but it is different from the normal DFA. The Atm can be partial, that is, every state in the Atm can be initial or final state.What follows are the formal definitions ofL(Atm) and MLCS recognized/accepted by the Atm.Definition 3.2.
ForAtm={Q,Σ,δ,Q0,F} defined by Definition 3.1, a character sequence x∈∑* is called to be recognized/accepted by the Atm if and only if for δ(Qi,a)∈Q′, where, Qi∈Q, Q′=Q-{Q0}={Q1,Q2,…,Qn}. L(Atm)={x∣x∈∑*,δ(Qi,x)∈Q′} is called a language recognized/accepted by Atm.Based on Definition3.2, we can easily deduce the following conclusion.Lemma 3.3.
ForAtm={Q,Σ,δ,Q0,F}, if for all x∈Σ* and δ(Q0,x)∈F, then
(3.3)MLCS={x∣x∈Σ*,δ(Q0,x)∈F,|x|=max(|x|)}.
That is, MLCS is the set of the longest sequences recognized/accepted by L(Atm).With Definition3.2, we can obtain the following properties.Theorem 3.4.
For allS∈MLCS, let β be the corresponding matched pair of the ith (i>1) character ci and α be the corresponding matched pair of the (i-1)th character ci-1 in sequence S, then, β must be the direct successive matched pair of α. Furthermore, the first character of S must belong to the character of an initial matched pair.Proof.
We give the proof by reduction in the following.
For allS∈MLCS, assuming that β is not the direct successive matched pair of α, there will be a matched pair γ (γ corresponds to character c) such that α<γ<β. So we can insert c between ci-1 and ci to get a longer common subsequence, denoted as MLCS’, which is contradiction to the fact that S is the longest common subsequence.
Then, let us consider the matched pairλ which corresponds to the first character of the S. If λ is not an initial matched pair, according to Definition 2.3, there must exist a matched pair ω, and ω<λ. So we can get a longer MLCS’ by inserting the character corresponding to ω into the header of the S which contradicts to the fact that S is the longest common subsequence.Theorem 3.5.
The Atm is a directed acyclic graph (DAG).Proof.
The theorem will be proved by reduction.
Suppose that there was a series of statesQi, Qj, and Qk forming a cycle in Atm, that is, state Qi is the successive state of state Qi, Qk is the successive state of Qj, and Qi is the successive state of Qk. Due to the fact that matched pairs pi, pj, and pk correspond to the states Qi, Qj, and Qk, we can get the results, pi<pj, pj<pk and pk<pi, which contradicts to Definition 2.2. Therefore, Atm is a directed acyclic graph.Theorem 3.6.
∑
a
∈
Σ
∏
i
=
1
d
|
S
i
′
|
a
+
1 is an upper bound of the number of Atm ’s states, where |Si′|a represents the occurrence number of a in sequence Si′.Proof.
Because the number of times the charactera appears in the sequence Si′ is less than or equal to |Si′|a, ∏i=1d|Si′|a is an upper bound for the number of the Atm’s states for the character a. Thus, ∑a∈Σ∏i=1d|Si′|a is an upper bound for all elements in Σ. By considering the initial state of the Atm, we get an upper bound ∑a∈Σ∏i=1d|Si′|a+1 of the number of the Atm’s states.


## 4. FACC Algorithm Based on MapReduce Parallel Framework of Cloud Computing

### 4.1. The Overview of the MapReduce Parallel Framework of Cloud Computing

For the convenience, we first briefly overview the MapReduce parallel framework of cloud computing.Cloud computing is a new computing model [24], which is a development of distributed computing, parallel computing and grid computing. MapReduce is a parallel framework of cloud computing and an associated implementation for processing and generating large datasets. It is amenable to a broad variety of real-world tasks and has been widely recognized as a cost-effective high performance parallel computing model. In the model, based on “divide and conquer” technology, users only specify the computation in terms of a mapand a reducefunction, and the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules intermachine communication to make efficient use of the network and disks [25, 26]. Figure 1 shows the execution framework of MapReduce [26].Figure 1
The execution framework of MapReduce.


### 4.2. The Proposed Algorithm: FACC

In this subsection, before describing the details of the proposed FACC, we first give its framework as follows.(1)
Preprocessing. Determine the common alphabet Σ of sequence set T, and preprocess every sequence of T as follows. The redundant characters in each sequence are filtered, that is, removing the characters which do not appear in at least one sequence in T. This process will ensure a quick searching later for MLCS of T.(2)
Construction of successor tables. Based on the MapReduce parallel framework of cloud computing, successor tables (see Section 4.2 Definition 4.1) for every preprocessed sequence of T are parallel constructed. Since any character in the MLCS should be a character corresponding to a matched pair, we can construct the successor table for each sequence so that all possible matched pairs of T can be found quickly.(3)
Construction of the finite automaton Atm for recognizing/accepting common subsequence. Based on the MapReduce parallel framework, and using the matched pairs as the states and adding an initial state to the Atm, we can construct the Atm which can recognize/accept all the CS of sequences of the T according to transition function of the Atm, wherein each state holding all of the states of its parent nodes during the construction of the Atm.(4)
Traversal of the Atm and output all of the MLCS. Search for the MLCS by traversing the Atm through the depth-first method.In the following, the proposed FACC and its implementation based on MapReduce will be described step by step in detail.


#### 4.2.1. Preprocessing

Recall that the MLCS ofT should be the sequences over their common alphabet Σ. The goal of the preprocessing is to reduce the searching time by filtering the redundant characters in each sequence which does not appear in Σ. After preprocessing, we will obtain the specific sequences which only reserve the characters in Σ. Since preprocessing leads to some time and space cost, the proposed FACC adopts this procedure only in the situations of the large or unknown alphabet Σ.The idea of the preprocessing is that aKey-Value table is designed (that is a data structure Map), where the Key represents a character α and the Value is the total number of the sequences containing character α. For N sequences, the Value corresponding to Keyα in the Map equals k if and only if k sequences contain the character α. Obviously, k≤N. In this situation, we call the value of Keyα is k. According to the definition of the value k of Keyα, we can see that all characters with value N consist of the alphabet Σ. Then, all sequences are filtered in parallel using the MapReduce of cloud computing and only the characters in Σ are reserved. The ith resulted sequence obtained from Si after the filter is denoted as Si′for i=1~N.Algorithm1 shows the pseudocode of the preprocessing algorithm.Algorithm 1:The pseudocode of the preprocessing algorithm.
AlgorithmPre-processing (InitStringSet)
Input:  InitStringSet: a initial string set.
Output: Σ:common alphabet overInitStringSet
StringSet: the result of pre-processed InitStringSet
(1)  for each stringSi in InitStringSet
(2)  tempSet =∅
(3)  for each characterSi[j] in Si
(4)   if (Si[j]∉tempSet)
(5)    tempSet = tempSet∪  {Si[j]}
(6)    if (Si[j] ∈ map)
(7)     map (Si[j]) = map (Si[j]) + 1
(8)    else
(9)     map (Si[j]) = 1
(10)  endfor
(11) endfor
(12)Σ=∅
(13) for each characterchar[i] in map
(14) if (map(char[i]) == size (InitStringSet))
(15)Σ = Σ  ∪  {char[i]}
(16) endfor
(17)StringSet = InitStringSet
(18) for each stringSi in StringSet
(19)  for each characterSi[j] in Si
(20)    if (Si[j] ∉Σ)
(21)     delete (Si[j])
(22)  endfor
(23) endfor
(24) returnΣ and StringSetFor example, sequencesS1=abecadbca and S2=acbafcgba, Σ1={a,b,c,d,e} and Σ2={a,b,c,f,g} are the alphabets of these two sequences, respectively. After preprocessing to S1 and S2, we can get Σ={a,b,c}, and S1 is converted into S1′=abcabca, and S2 is converted into S2′=acbacba.


#### 4.2.2. Successor Table

LetTabk denote the successor table of the sequence Sk and its definition is as follows.Definition 4.1.
For a sequenceSk=x1,x2,x3,…,xn drawn from alphabet Σk=(σ1,σ2,…,σt), the successor table Tabk of the sequence Sk is an irregular two-dimensional table, where the element of ith row and jth column of the table Tabk is denoted as Tabk[i,j], which is defined as follow. 											(4.1)Tabk[i,j]=min{p∣xp=σi,p≥1,p≥j,p<n,1≤i≤|Σk|,1≤j≤n}.The value ofTabk[i,j] indicates the minimal subscript position p of the sequence Sk=x1,x2,x3,…,xn according to σi after position j when xp=σi.For the two sequencesS1′=abcabca and S2′=acbacba, Tables 2 and 3 show the successor tables of them.Table 2
Successor table Tab1 of S1′.
a
1
4
4
4
7
7
7
b
2
2
5
5
5
c
3
3
3
6
6
6Table 3
Successor table Tab2 of S2′.
a
1
4
4
4
7
7
7
b
3
3
3
6
6
6
c
2
2
5
5
5To construct successor tables forT, We dispatch |T| Map functions to construct successor table for each sequence of T in parallel, and then employ a Reduce function to aggregate the successor tables of the sequences of T.Because the irregular successor tables only store the useful information and are constructed in parallel, it can considerably reduce the time and space complexity of searching for the MLCS.With the constructed successor table, a direct successive matched pair of a matched pair can be gotten quickly. Take Tab1 and Tab2 as examples. When searching for the successive matched pairs of matched pair [i,j], all we need to do is searching for the matched pairs of the [Tab1(i), Tab2(j)], (where Tab1(i) and Tab2(j) stand for all the elements of the ith and jth columns in the Tab1 and Tab2, respectively), and then, removes all of the matched pairs which are not direct successive matched pairs. For example, by checking Tab1 and Tab2 based on Definition 4.1, we can get the following successive matched pairs [4,4], [2,3], and [3,2] of matched pair [1,1]. Due to [2,3] < [4,4] and [3,2] < [4,4], we remove indirect successive matched pair [4,4], and finally, get the expected direct successive matched pairs [2,3] and [3,2] of the matched pair [1,1].


#### 4.2.3. Constructing the Common SubsequenceAtm of T

By the aforementioned Definition3.1 and its properties of the Atm, we can build the common subsequence Atm of the sequence set T in parallel by MapReduce. The algorithm Build-Atm is shown in Algorithm 2.Algorithm 2:The pseudocode for constructing Atm in parallel by MapReduce.
AlgorithmBuild-Atm(Pos, dsucSet)
Input:  Q0: the initial state of the Atm(0,0,…,0)
tabSet: the set of successor tables for T drawn from Σ
Output: Atm: a Atm of T for MLCS
(1)Atm = NULL, Q={Q0}
(2)  Build-Atm(Q, tabSet)
(3)dispatch |Q| map functions in parallel do
(4)for each Qi∈Q, for ∀a∈Σ dispatch a Map function
(5) Qj=δ(Qi,a)
(6)if Qj∉Q and Qj≠Φ
(7)Q=Q∪Qj
(8)end for
(9)reduce all the results of the Map functions
(10) reduce all the results of the Map functions
(11) Build-Atm(Q, tabSet)
(12) returnAtm
(13) endWith the algorithm shown in Algorithm2, take two sequences S1′ and S2′ for example, the main construction process of the Atm can be shown as follows (the process also applies to multiple sequences of T). (1) Construct a virtual initial state (0,0) corresponding to the matched pair [0,0] with character ε. (2) Determine all of the direct successive matched pairs of the matched pair [0,0]. (3) Use the deep first search (DFS) method to construct the Atm.Notice that each state in theAtm must remember all of the states of its parent nodes during the construction of the Atm. For example, two sequences S1′ and S2′ illustrated in Figure 2 have a direct successive matched pair [1,1] of the matched pair [0,0]. Because matched pair [1,1] corresponds to character a, we can get a state transition δ((0,0),a)=(1,1). By the algorithm shown in Algorithm 2. The final common subsequence Atm constructed in the example of Figure 2 is shown in Figure 3, where the states (0,0) and (7,7) are the initial and final states of the Atm of the sequences S1′ and S2′, respectively.Figure 2
SequencesS1′ and S2′.Figure 3
The common subsequenceAtm of the sequences S1′ and S2′.


#### 4.2.4. TraversingAtm and Finding the MCLS

By the finite automata theory and Definitions3.1 and 3.2, we can get a character sequence, corresponding to a path from Q0 to a state of the F of Atm, which is a candidate longest common subsequence of T, named LCS′. Hence, all the longest character sequences of all the candidate sequences are exactly the elements of MLCS from T. We first design a specific set named resultSet to store the expected MLCS. Then, By the depth first search method, the Atm is traversed from Q0 to every state of the F in parallel by MapReduce schemes. Once we get a candidate LCS′, we make following operations: if resultSet is not empty and all string length of elements in resultSet is longer than that of the LCS′, ignore the LCS′; otherwise clear resultSet, and then insert LCS′ into the resultSet. Because resultSet is a set, it can eliminateredundant elements automatically, hence, we can acquire the MLCS from the resultSet eventually. In the example for the sequences S1′ and S2′ the all MLCSs are {abcba,ababa,acaca,acbca,acaba,abaca}.


## 4.1. The Overview of the MapReduce Parallel Framework of Cloud Computing

For the convenience, we first briefly overview the MapReduce parallel framework of cloud computing.Cloud computing is a new computing model [24], which is a development of distributed computing, parallel computing and grid computing. MapReduce is a parallel framework of cloud computing and an associated implementation for processing and generating large datasets. It is amenable to a broad variety of real-world tasks and has been widely recognized as a cost-effective high performance parallel computing model. In the model, based on “divide and conquer” technology, users only specify the computation in terms of a mapand a reducefunction, and the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules intermachine communication to make efficient use of the network and disks [25, 26]. Figure 1 shows the execution framework of MapReduce [26].Figure 1
The execution framework of MapReduce.


## 4.2. The Proposed Algorithm: FACC

In this subsection, before describing the details of the proposed FACC, we first give its framework as follows.(1)
Preprocessing. Determine the common alphabet Σ of sequence set T, and preprocess every sequence of T as follows. The redundant characters in each sequence are filtered, that is, removing the characters which do not appear in at least one sequence in T. This process will ensure a quick searching later for MLCS of T.(2)
Construction of successor tables. Based on the MapReduce parallel framework of cloud computing, successor tables (see Section 4.2 Definition 4.1) for every preprocessed sequence of T are parallel constructed. Since any character in the MLCS should be a character corresponding to a matched pair, we can construct the successor table for each sequence so that all possible matched pairs of T can be found quickly.(3)
Construction of the finite automaton Atm for recognizing/accepting common subsequence. Based on the MapReduce parallel framework, and using the matched pairs as the states and adding an initial state to the Atm, we can construct the Atm which can recognize/accept all the CS of sequences of the T according to transition function of the Atm, wherein each state holding all of the states of its parent nodes during the construction of the Atm.(4)
Traversal of the Atm and output all of the MLCS. Search for the MLCS by traversing the Atm through the depth-first method.In the following, the proposed FACC and its implementation based on MapReduce will be described step by step in detail.


### 4.2.1. Preprocessing

Recall that the MLCS ofT should be the sequences over their common alphabet Σ. The goal of the preprocessing is to reduce the searching time by filtering the redundant characters in each sequence which does not appear in Σ. After preprocessing, we will obtain the specific sequences which only reserve the characters in Σ. Since preprocessing leads to some time and space cost, the proposed FACC adopts this procedure only in the situations of the large or unknown alphabet Σ.The idea of the preprocessing is that aKey-Value table is designed (that is a data structure Map), where the Key represents a character α and the Value is the total number of the sequences containing character α. For N sequences, the Value corresponding to Keyα in the Map equals k if and only if k sequences contain the character α. Obviously, k≤N. In this situation, we call the value of Keyα is k. According to the definition of the value k of Keyα, we can see that all characters with value N consist of the alphabet Σ. Then, all sequences are filtered in parallel using the MapReduce of cloud computing and only the characters in Σ are reserved. The ith resulted sequence obtained from Si after the filter is denoted as Si′for i=1~N.Algorithm1 shows the pseudocode of the preprocessing algorithm.Algorithm 1:The pseudocode of the preprocessing algorithm.
AlgorithmPre-processing (InitStringSet)
Input:  InitStringSet: a initial string set.
Output: Σ:common alphabet overInitStringSet
StringSet: the result of pre-processed InitStringSet
(1)  for each stringSi in InitStringSet
(2)  tempSet =∅
(3)  for each characterSi[j] in Si
(4)   if (Si[j]∉tempSet)
(5)    tempSet = tempSet∪  {Si[j]}
(6)    if (Si[j] ∈ map)
(7)     map (Si[j]) = map (Si[j]) + 1
(8)    else
(9)     map (Si[j]) = 1
(10)  endfor
(11) endfor
(12)Σ=∅
(13) for each characterchar[i] in map
(14) if (map(char[i]) == size (InitStringSet))
(15)Σ = Σ  ∪  {char[i]}
(16) endfor
(17)StringSet = InitStringSet
(18) for each stringSi in StringSet
(19)  for each characterSi[j] in Si
(20)    if (Si[j] ∉Σ)
(21)     delete (Si[j])
(22)  endfor
(23) endfor
(24) returnΣ and StringSetFor example, sequencesS1=abecadbca and S2=acbafcgba, Σ1={a,b,c,d,e} and Σ2={a,b,c,f,g} are the alphabets of these two sequences, respectively. After preprocessing to S1 and S2, we can get Σ={a,b,c}, and S1 is converted into S1′=abcabca, and S2 is converted into S2′=acbacba.


### 4.2.2. Successor Table

LetTabk denote the successor table of the sequence Sk and its definition is as follows.Definition 4.1.
For a sequenceSk=x1,x2,x3,…,xn drawn from alphabet Σk=(σ1,σ2,…,σt), the successor table Tabk of the sequence Sk is an irregular two-dimensional table, where the element of ith row and jth column of the table Tabk is denoted as Tabk[i,j], which is defined as follow. 											(4.1)Tabk[i,j]=min{p∣xp=σi,p≥1,p≥j,p<n,1≤i≤|Σk|,1≤j≤n}.The value ofTabk[i,j] indicates the minimal subscript position p of the sequence Sk=x1,x2,x3,…,xn according to σi after position j when xp=σi.For the two sequencesS1′=abcabca and S2′=acbacba, Tables 2 and 3 show the successor tables of them.Table 2
Successor table Tab1 of S1′.
a
1
4
4
4
7
7
7
b
2
2
5
5
5
c
3
3
3
6
6
6Table 3
Successor table Tab2 of S2′.
a
1
4
4
4
7
7
7
b
3
3
3
6
6
6
c
2
2
5
5
5To construct successor tables forT, We dispatch |T| Map functions to construct successor table for each sequence of T in parallel, and then employ a Reduce function to aggregate the successor tables of the sequences of T.Because the irregular successor tables only store the useful information and are constructed in parallel, it can considerably reduce the time and space complexity of searching for the MLCS.With the constructed successor table, a direct successive matched pair of a matched pair can be gotten quickly. Take Tab1 and Tab2 as examples. When searching for the successive matched pairs of matched pair [i,j], all we need to do is searching for the matched pairs of the [Tab1(i), Tab2(j)], (where Tab1(i) and Tab2(j) stand for all the elements of the ith and jth columns in the Tab1 and Tab2, respectively), and then, removes all of the matched pairs which are not direct successive matched pairs. For example, by checking Tab1 and Tab2 based on Definition 4.1, we can get the following successive matched pairs [4,4], [2,3], and [3,2] of matched pair [1,1]. Due to [2,3] < [4,4] and [3,2] < [4,4], we remove indirect successive matched pair [4,4], and finally, get the expected direct successive matched pairs [2,3] and [3,2] of the matched pair [1,1].


### 4.2.3. Constructing the Common SubsequenceAtm of T

By the aforementioned Definition3.1 and its properties of the Atm, we can build the common subsequence Atm of the sequence set T in parallel by MapReduce. The algorithm Build-Atm is shown in Algorithm 2.Algorithm 2:The pseudocode for constructing Atm in parallel by MapReduce.
AlgorithmBuild-Atm(Pos, dsucSet)
Input:  Q0: the initial state of the Atm(0,0,…,0)
tabSet: the set of successor tables for T drawn from Σ
Output: Atm: a Atm of T for MLCS
(1)Atm = NULL, Q={Q0}
(2)  Build-Atm(Q, tabSet)
(3)dispatch |Q| map functions in parallel do
(4)for each Qi∈Q, for ∀a∈Σ dispatch a Map function
(5) Qj=δ(Qi,a)
(6)if Qj∉Q and Qj≠Φ
(7)Q=Q∪Qj
(8)end for
(9)reduce all the results of the Map functions
(10) reduce all the results of the Map functions
(11) Build-Atm(Q, tabSet)
(12) returnAtm
(13) endWith the algorithm shown in Algorithm2, take two sequences S1′ and S2′ for example, the main construction process of the Atm can be shown as follows (the process also applies to multiple sequences of T). (1) Construct a virtual initial state (0,0) corresponding to the matched pair [0,0] with character ε. (2) Determine all of the direct successive matched pairs of the matched pair [0,0]. (3) Use the deep first search (DFS) method to construct the Atm.Notice that each state in theAtm must remember all of the states of its parent nodes during the construction of the Atm. For example, two sequences S1′ and S2′ illustrated in Figure 2 have a direct successive matched pair [1,1] of the matched pair [0,0]. Because matched pair [1,1] corresponds to character a, we can get a state transition δ((0,0),a)=(1,1). By the algorithm shown in Algorithm 2. The final common subsequence Atm constructed in the example of Figure 2 is shown in Figure 3, where the states (0,0) and (7,7) are the initial and final states of the Atm of the sequences S1′ and S2′, respectively.Figure 2
SequencesS1′ and S2′.Figure 3
The common subsequenceAtm of the sequences S1′ and S2′.


### 4.2.4. TraversingAtm and Finding the MCLS

By the finite automata theory and Definitions3.1 and 3.2, we can get a character sequence, corresponding to a path from Q0 to a state of the F of Atm, which is a candidate longest common subsequence of T, named LCS′. Hence, all the longest character sequences of all the candidate sequences are exactly the elements of MLCS from T. We first design a specific set named resultSet to store the expected MLCS. Then, By the depth first search method, the Atm is traversed from Q0 to every state of the F in parallel by MapReduce schemes. Once we get a candidate LCS′, we make following operations: if resultSet is not empty and all string length of elements in resultSet is longer than that of the LCS′, ignore the LCS′; otherwise clear resultSet, and then insert LCS′ into the resultSet. Because resultSet is a set, it can eliminateredundant elements automatically, hence, we can acquire the MLCS from the resultSet eventually. In the example for the sequences S1′ and S2′ the all MLCSs are {abcba,ababa,acaca,acbca,acaba,abaca}.


## 4.2.1. Preprocessing

Recall that the MLCS ofT should be the sequences over their common alphabet Σ. The goal of the preprocessing is to reduce the searching time by filtering the redundant characters in each sequence which does not appear in Σ. After preprocessing, we will obtain the specific sequences which only reserve the characters in Σ. Since preprocessing leads to some time and space cost, the proposed FACC adopts this procedure only in the situations of the large or unknown alphabet Σ.The idea of the preprocessing is that aKey-Value table is designed (that is a data structure Map), where the Key represents a character α and the Value is the total number of the sequences containing character α. For N sequences, the Value corresponding to Keyα in the Map equals k if and only if k sequences contain the character α. Obviously, k≤N. In this situation, we call the value of Keyα is k. According to the definition of the value k of Keyα, we can see that all characters with value N consist of the alphabet Σ. Then, all sequences are filtered in parallel using the MapReduce of cloud computing and only the characters in Σ are reserved. The ith resulted sequence obtained from Si after the filter is denoted as Si′for i=1~N.Algorithm1 shows the pseudocode of the preprocessing algorithm.Algorithm 1:The pseudocode of the preprocessing algorithm.
AlgorithmPre-processing (InitStringSet)
Input:  InitStringSet: a initial string set.
Output: Σ:common alphabet overInitStringSet
StringSet: the result of pre-processed InitStringSet
(1)  for each stringSi in InitStringSet
(2)  tempSet =∅
(3)  for each characterSi[j] in Si
(4)   if (Si[j]∉tempSet)
(5)    tempSet = tempSet∪  {Si[j]}
(6)    if (Si[j] ∈ map)
(7)     map (Si[j]) = map (Si[j]) + 1
(8)    else
(9)     map (Si[j]) = 1
(10)  endfor
(11) endfor
(12)Σ=∅
(13) for each characterchar[i] in map
(14) if (map(char[i]) == size (InitStringSet))
(15)Σ = Σ  ∪  {char[i]}
(16) endfor
(17)StringSet = InitStringSet
(18) for each stringSi in StringSet
(19)  for each characterSi[j] in Si
(20)    if (Si[j] ∉Σ)
(21)     delete (Si[j])
(22)  endfor
(23) endfor
(24) returnΣ and StringSetFor example, sequencesS1=abecadbca and S2=acbafcgba, Σ1={a,b,c,d,e} and Σ2={a,b,c,f,g} are the alphabets of these two sequences, respectively. After preprocessing to S1 and S2, we can get Σ={a,b,c}, and S1 is converted into S1′=abcabca, and S2 is converted into S2′=acbacba.


## 4.2.2. Successor Table

LetTabk denote the successor table of the sequence Sk and its definition is as follows.Definition 4.1.
For a sequenceSk=x1,x2,x3,…,xn drawn from alphabet Σk=(σ1,σ2,…,σt), the successor table Tabk of the sequence Sk is an irregular two-dimensional table, where the element of ith row and jth column of the table Tabk is denoted as Tabk[i,j], which is defined as follow. 											(4.1)Tabk[i,j]=min{p∣xp=σi,p≥1,p≥j,p<n,1≤i≤|Σk|,1≤j≤n}.The value ofTabk[i,j] indicates the minimal subscript position p of the sequence Sk=x1,x2,x3,…,xn according to σi after position j when xp=σi.For the two sequencesS1′=abcabca and S2′=acbacba, Tables 2 and 3 show the successor tables of them.Table 2
Successor table Tab1 of S1′.
a
1
4
4
4
7
7
7
b
2
2
5
5
5
c
3
3
3
6
6
6Table 3
Successor table Tab2 of S2′.
a
1
4
4
4
7
7
7
b
3
3
3
6
6
6
c
2
2
5
5
5To construct successor tables forT, We dispatch |T| Map functions to construct successor table for each sequence of T in parallel, and then employ a Reduce function to aggregate the successor tables of the sequences of T.Because the irregular successor tables only store the useful information and are constructed in parallel, it can considerably reduce the time and space complexity of searching for the MLCS.With the constructed successor table, a direct successive matched pair of a matched pair can be gotten quickly. Take Tab1 and Tab2 as examples. When searching for the successive matched pairs of matched pair [i,j], all we need to do is searching for the matched pairs of the [Tab1(i), Tab2(j)], (where Tab1(i) and Tab2(j) stand for all the elements of the ith and jth columns in the Tab1 and Tab2, respectively), and then, removes all of the matched pairs which are not direct successive matched pairs. For example, by checking Tab1 and Tab2 based on Definition 4.1, we can get the following successive matched pairs [4,4], [2,3], and [3,2] of matched pair [1,1]. Due to [2,3] < [4,4] and [3,2] < [4,4], we remove indirect successive matched pair [4,4], and finally, get the expected direct successive matched pairs [2,3] and [3,2] of the matched pair [1,1].


## 4.2.3. Constructing the Common SubsequenceAtm of T

By the aforementioned Definition3.1 and its properties of the Atm, we can build the common subsequence Atm of the sequence set T in parallel by MapReduce. The algorithm Build-Atm is shown in Algorithm 2.Algorithm 2:The pseudocode for constructing Atm in parallel by MapReduce.
AlgorithmBuild-Atm(Pos, dsucSet)
Input:  Q0: the initial state of the Atm(0,0,…,0)
tabSet: the set of successor tables for T drawn from Σ
Output: Atm: a Atm of T for MLCS
(1)Atm = NULL, Q={Q0}
(2)  Build-Atm(Q, tabSet)
(3)dispatch |Q| map functions in parallel do
(4)for each Qi∈Q, for ∀a∈Σ dispatch a Map function
(5) Qj=δ(Qi,a)
(6)if Qj∉Q and Qj≠Φ
(7)Q=Q∪Qj
(8)end for
(9)reduce all the results of the Map functions
(10) reduce all the results of the Map functions
(11) Build-Atm(Q, tabSet)
(12) returnAtm
(13) endWith the algorithm shown in Algorithm2, take two sequences S1′ and S2′ for example, the main construction process of the Atm can be shown as follows (the process also applies to multiple sequences of T). (1) Construct a virtual initial state (0,0) corresponding to the matched pair [0,0] with character ε. (2) Determine all of the direct successive matched pairs of the matched pair [0,0]. (3) Use the deep first search (DFS) method to construct the Atm.Notice that each state in theAtm must remember all of the states of its parent nodes during the construction of the Atm. For example, two sequences S1′ and S2′ illustrated in Figure 2 have a direct successive matched pair [1,1] of the matched pair [0,0]. Because matched pair [1,1] corresponds to character a, we can get a state transition δ((0,0),a)=(1,1). By the algorithm shown in Algorithm 2. The final common subsequence Atm constructed in the example of Figure 2 is shown in Figure 3, where the states (0,0) and (7,7) are the initial and final states of the Atm of the sequences S1′ and S2′, respectively.Figure 2
SequencesS1′ and S2′.Figure 3
The common subsequenceAtm of the sequences S1′ and S2′.


## 4.2.4. TraversingAtm and Finding the MCLS

By the finite automata theory and Definitions3.1 and 3.2, we can get a character sequence, corresponding to a path from Q0 to a state of the F of Atm, which is a candidate longest common subsequence of T, named LCS′. Hence, all the longest character sequences of all the candidate sequences are exactly the elements of MLCS from T. We first design a specific set named resultSet to store the expected MLCS. Then, By the depth first search method, the Atm is traversed from Q0 to every state of the F in parallel by MapReduce schemes. Once we get a candidate LCS′, we make following operations: if resultSet is not empty and all string length of elements in resultSet is longer than that of the LCS′, ignore the LCS′; otherwise clear resultSet, and then insert LCS′ into the resultSet. Because resultSet is a set, it can eliminateredundant elements automatically, hence, we can acquire the MLCS from the resultSet eventually. In the example for the sequences S1′ and S2′ the all MLCSs are {abcba,ababa,acaca,acbca,acaba,abaca}.


## 5. The Time and Space Complexity Analysis of FACC

### 5.1. Time Complexity

In what follows, we first give the time complexity of the FACC in every stage, and then the total time complexity.Preprocessing
It is necessary to traverse every sequence ofT once in order to find its common alphabet, therefore the step is O(∑i=1d|Si|) time, where |Si| is the length of a sequence Si and d is the number of total sequences of T, that is, d=|T|. It is also necessary to traverse every sequence of T to filter the characters not in Σ, which also requires O(∑i=1d|Si|) time complexity. Assuming all the sequences in T with the same length n and the number of Map functions is d, the total time complexity is O(n) in the stage based on MapReduce schemes.Constructing the Successor Table
To build successor tables for all of the sequences pre-processed, it is necessary to traverse these sequences once again. It turns out that the same time complexity is required as the above preprocessing stage based on MapReduce schemes.ConstructingAtm
According to Theorem3.6, it is known that the upper bound for the number of the Atm’s states is ∑a∈Σ∏i=1d|Si′|a+1, where |Si′|a stands for the number of times character a appears in the sequence Si′. Because the time complexity for constructing the Atm is proportional to the number of the Atm’s states |Q|, the time complexity for constructing the Atm is O(|Q|) in this stage based on MapReduce schemes.Thus, the total time complexity of FACC is equal toO(n)+O(n)+O(|Q|)=max{O(n),O(|Q|)}.


### 5.2. Space Complexity

Because the storage space of sequences and successor tables is static and proportional to the size ofT, the space complexity of their storage is O(∑i=1d|Si|). For building the Atm, the storage space is proportional to the number of states, hence the space complexity for building the Atm is O(∑a∈Σ∏i=1d|Si′|a). On the other hand, in recursively constructing the Atm, on the average, the recursion depth is log(∑a∈Σ∏i=1d|Si′|a), and then the space complexity required temporary space is O(log(∑a∈Σ∏i=1d|Si′|a)) for constructing and traversing the Atm. It happens that the space complexity of FACC is
(5.1)O(∑i=1d|Si|)+O(∑a∈Σ∏i=1d|Si′|a)+O(log(∑a∈Σ∏i=1d|Si′|a))+O(log(∑a∈Σ∏i=1d|Si′|a))=O(∑i=1d|Si|+∑a∈Σ∏i=1d|Si′|a).


## 5.1. Time Complexity

In what follows, we first give the time complexity of the FACC in every stage, and then the total time complexity.Preprocessing
It is necessary to traverse every sequence ofT once in order to find its common alphabet, therefore the step is O(∑i=1d|Si|) time, where |Si| is the length of a sequence Si and d is the number of total sequences of T, that is, d=|T|. It is also necessary to traverse every sequence of T to filter the characters not in Σ, which also requires O(∑i=1d|Si|) time complexity. Assuming all the sequences in T with the same length n and the number of Map functions is d, the total time complexity is O(n) in the stage based on MapReduce schemes.Constructing the Successor Table
To build successor tables for all of the sequences pre-processed, it is necessary to traverse these sequences once again. It turns out that the same time complexity is required as the above preprocessing stage based on MapReduce schemes.ConstructingAtm
According to Theorem3.6, it is known that the upper bound for the number of the Atm’s states is ∑a∈Σ∏i=1d|Si′|a+1, where |Si′|a stands for the number of times character a appears in the sequence Si′. Because the time complexity for constructing the Atm is proportional to the number of the Atm’s states |Q|, the time complexity for constructing the Atm is O(|Q|) in this stage based on MapReduce schemes.Thus, the total time complexity of FACC is equal toO(n)+O(n)+O(|Q|)=max{O(n),O(|Q|)}.


## 5.2. Space Complexity

Because the storage space of sequences and successor tables is static and proportional to the size ofT, the space complexity of their storage is O(∑i=1d|Si|). For building the Atm, the storage space is proportional to the number of states, hence the space complexity for building the Atm is O(∑a∈Σ∏i=1d|Si′|a). On the other hand, in recursively constructing the Atm, on the average, the recursion depth is log(∑a∈Σ∏i=1d|Si′|a), and then the space complexity required temporary space is O(log(∑a∈Σ∏i=1d|Si′|a)) for constructing and traversing the Atm. It happens that the space complexity of FACC is
(5.1)O(∑i=1d|Si|)+O(∑a∈Σ∏i=1d|Si′|a)+O(log(∑a∈Σ∏i=1d|Si′|a))+O(log(∑a∈Σ∏i=1d|Si′|a))=O(∑i=1d|Si|+∑a∈Σ∏i=1d|Si′|a).


## 6. Experiments and Analysis of Experimental Results

### 6.1. Dataset and Experimental Results

In this paper, to test the time performance of FACC and FAST-LCS fairly, we run the two algorithms on the same hardware platform. Using the DNA and amino acid sample sequences dataset provided by ncbi [27] and dip [28], we tested the proposed algorithm FACC on the Hadoop cluster with 4 worker nodes, each of which contains 2 Intel CPUs (2.67 GHz) X5550, 8 GB of RAM, and 24 GB of local disk allocated to HDFS. In the cluster each node was running Hadoop version 0.20.0 on RedHat Enterprise Linux Server release 5.3 and connected by 100 M Ethernet to a commodity switch. The FAST-LCS algorithm was run on 4×2 Intel CPUs (2.67 GHz) X5550, and 8 GB of RAM, using the same datasets and operating system, and the programming environment of the algorithms is JDK 1.7. The comparisons of the time performance between FACC and FAST-LCS are shown in Tables 4 and 5 and Figures 4 and 5.Table 4
Performance comparison between FAST-LCS and FACC on 20 DNA sequences(|Σ|=4) with lengths from 25 to 180.
|
S
i
|
FAST-LCS algorithm
FACC algorithm
AT (ms)
|
MLCS
|
N
MLCS
Precision
AT (ms)
|
MLCS
|
N
MLCS
Precision
TPR
25
8
14
7
0.88
13
14
8
1.00
0.62
50
21
23
2
1.00
32
23
2
1.00
0.66
75
747
33
8
0.80
545
33
10
1.00
1.37
100
12952
42
2
1.00
6859
42
2
1.00
1.89
110
38341
50
4
1.00
19951
50
4
1.00
1.92
120
84738
54
9
1.00
39218
54
9
1.00
2.16
130
256214
59
48
0.98
81781
59
49
1.00
3.13
140
614583
64
46
0.96
164817
64
48
1.00
3.73
150
1188403
69
2
1.00
333625
69
2
1.00
3.56
160
2417387
76
4
1.00
650569
76
4
1.00
3.72
170
4828904
79
10
0.83
1268609
79
12
1.00
3.81
180
9811863
85
2
1.00
2473788
85
2
1.00
3.97Table 5
Performance comparison between FAST-LCS and FACC on the 20 amino acid sequences(|Σ|=20) with lengths from 25 to 320.
|
S
i
|
FAST-LCS algorithm
FACC algorithm
Time (ms)
|
MLCS
|
N
MLCS
Precision
T (ms)
|
MLCS
|
N
MLCS
Precision
TPR
25
96
3
11
1.00
104
3
11
1.00
0.92
50
171
5
2
1.00
158
5
2
1.00
1.08
75
682
8
26
1.00
373
8
26
1.00
1.83
100
1177
14
1
1.00
601
14
1
1.00
1.96
120
2489
19
8
1.00
1210
19
8
1.00
2.06
140
4161
20
109
0.92
2006
20
119
1.00
2.07
160
14460
28
190
0.98
7192
28
194
1.00
2.01
180
32245
32
62
0.95
15807
32
65
1.00
2.04
200
69332
36
22
1.00
33803
36
22
1.00
2.05
220
140677
38
534
0.99
67889
38
539
1.00
2.07
240
269059
42
353
1.00
127409
42
353
1.00
2.11
260
497177
47
637
0.98
217605
47
650
1.00
2.28
280
1116905
49
8689
1.00
478707
49
8728
1.00
2.33
300
1617748
53
454
0.98
658212
53
462
1.00
2.46
320
2951500
60
201
0.96
1129275
60
210
1.00
2.61
Note: TPR indicates the ratio of the running time of FAST-LCS to that of FACC in Table5.Figure 4
The time performance comparison between FACC and FAST-LCS on 20 DNA sequences (|Σ|=4) with lengths from 25 to 180.Figure 5
The time performance comparison between FACC and FAST-LCS on 20 amino acid sequences (|Σ|=20) with lengths from 25 to 320.


### 6.2. Discussion of Experimental Results

Tables4 and 5 compares various performance indices of FAST-LCS and FACC on 20 DNA sequences (|Σ|=4) and 20 amino acid sequences (|Σ|=20) with different lengths of input sequences. It can be seen that various performance indices of FACC are superior to those of FAST-LCS, wherein the precision of FACC reaches 100% (shown in column Precision, which is the ratio of the number of found MLCSs NMLCS to the total number of MLCSs, of Tables 4 and 5), while that of FAST-LCS reaches 95% due to its incorrect pruning operation 2. Moreover, Tables 4 and 5 and Figures 4 and 5 show that the time performance of FACC considerably outperforms that of FAST-LCS, and with the increasing lengths of input sequences, the advantage of FACC is growing significantly over FAST-LCS.Figure6 shows the time performance of the proposed FACC with preprocessing and without preprocessing. It can be seen from Figure 6 that the time performance for the case with preprocessing is obviously superior to that without preprocessing, especially for the cases of a large set of alphabet and a long average length of sequences. Furthermore, the more the number of input sequences, the more efficient the proposed FACC.Figure 6
Performance of FACC with/without preprocessing on 20 amino acid sequences (|Σ|=20) with lengths from 70 to 170.In summary, the time performance of the proposed algorithm FACC is much better than that of FAST-LCS.


## 6.1. Dataset and Experimental Results

In this paper, to test the time performance of FACC and FAST-LCS fairly, we run the two algorithms on the same hardware platform. Using the DNA and amino acid sample sequences dataset provided by ncbi [27] and dip [28], we tested the proposed algorithm FACC on the Hadoop cluster with 4 worker nodes, each of which contains 2 Intel CPUs (2.67 GHz) X5550, 8 GB of RAM, and 24 GB of local disk allocated to HDFS. In the cluster each node was running Hadoop version 0.20.0 on RedHat Enterprise Linux Server release 5.3 and connected by 100 M Ethernet to a commodity switch. The FAST-LCS algorithm was run on 4×2 Intel CPUs (2.67 GHz) X5550, and 8 GB of RAM, using the same datasets and operating system, and the programming environment of the algorithms is JDK 1.7. The comparisons of the time performance between FACC and FAST-LCS are shown in Tables 4 and 5 and Figures 4 and 5.Table 4
Performance comparison between FAST-LCS and FACC on 20 DNA sequences(|Σ|=4) with lengths from 25 to 180.
|
S
i
|
FAST-LCS algorithm
FACC algorithm
AT (ms)
|
MLCS
|
N
MLCS
Precision
AT (ms)
|
MLCS
|
N
MLCS
Precision
TPR
25
8
14
7
0.88
13
14
8
1.00
0.62
50
21
23
2
1.00
32
23
2
1.00
0.66
75
747
33
8
0.80
545
33
10
1.00
1.37
100
12952
42
2
1.00
6859
42
2
1.00
1.89
110
38341
50
4
1.00
19951
50
4
1.00
1.92
120
84738
54
9
1.00
39218
54
9
1.00
2.16
130
256214
59
48
0.98
81781
59
49
1.00
3.13
140
614583
64
46
0.96
164817
64
48
1.00
3.73
150
1188403
69
2
1.00
333625
69
2
1.00
3.56
160
2417387
76
4
1.00
650569
76
4
1.00
3.72
170
4828904
79
10
0.83
1268609
79
12
1.00
3.81
180
9811863
85
2
1.00
2473788
85
2
1.00
3.97Table 5
Performance comparison between FAST-LCS and FACC on the 20 amino acid sequences(|Σ|=20) with lengths from 25 to 320.
|
S
i
|
FAST-LCS algorithm
FACC algorithm
Time (ms)
|
MLCS
|
N
MLCS
Precision
T (ms)
|
MLCS
|
N
MLCS
Precision
TPR
25
96
3
11
1.00
104
3
11
1.00
0.92
50
171
5
2
1.00
158
5
2
1.00
1.08
75
682
8
26
1.00
373
8
26
1.00
1.83
100
1177
14
1
1.00
601
14
1
1.00
1.96
120
2489
19
8
1.00
1210
19
8
1.00
2.06
140
4161
20
109
0.92
2006
20
119
1.00
2.07
160
14460
28
190
0.98
7192
28
194
1.00
2.01
180
32245
32
62
0.95
15807
32
65
1.00
2.04
200
69332
36
22
1.00
33803
36
22
1.00
2.05
220
140677
38
534
0.99
67889
38
539
1.00
2.07
240
269059
42
353
1.00
127409
42
353
1.00
2.11
260
497177
47
637
0.98
217605
47
650
1.00
2.28
280
1116905
49
8689
1.00
478707
49
8728
1.00
2.33
300
1617748
53
454
0.98
658212
53
462
1.00
2.46
320
2951500
60
201
0.96
1129275
60
210
1.00
2.61
Note: TPR indicates the ratio of the running time of FAST-LCS to that of FACC in Table5.Figure 4
The time performance comparison between FACC and FAST-LCS on 20 DNA sequences (|Σ|=4) with lengths from 25 to 180.Figure 5
The time performance comparison between FACC and FAST-LCS on 20 amino acid sequences (|Σ|=20) with lengths from 25 to 320.


## 6.2. Discussion of Experimental Results

Tables4 and 5 compares various performance indices of FAST-LCS and FACC on 20 DNA sequences (|Σ|=4) and 20 amino acid sequences (|Σ|=20) with different lengths of input sequences. It can be seen that various performance indices of FACC are superior to those of FAST-LCS, wherein the precision of FACC reaches 100% (shown in column Precision, which is the ratio of the number of found MLCSs NMLCS to the total number of MLCSs, of Tables 4 and 5), while that of FAST-LCS reaches 95% due to its incorrect pruning operation 2. Moreover, Tables 4 and 5 and Figures 4 and 5 show that the time performance of FACC considerably outperforms that of FAST-LCS, and with the increasing lengths of input sequences, the advantage of FACC is growing significantly over FAST-LCS.Figure6 shows the time performance of the proposed FACC with preprocessing and without preprocessing. It can be seen from Figure 6 that the time performance for the case with preprocessing is obviously superior to that without preprocessing, especially for the cases of a large set of alphabet and a long average length of sequences. Furthermore, the more the number of input sequences, the more efficient the proposed FACC.Figure 6
Performance of FACC with/without preprocessing on 20 amino acid sequences (|Σ|=20) with lengths from 70 to 170.In summary, the time performance of the proposed algorithm FACC is much better than that of FAST-LCS.


## 7. Conclusions

Considering that the efficiency and effectiveness of the existing parallel algorithms for searching for MLCS are not satisfactory with the increasing complexity and size of biologic data and do not give an abstract and formal description of the MLCS problem and adopt complicated parallel schemes, we propose a novel finite automaton based on MapReduce parallel framework of cloud computing called FACC to overcome the existing algorithms’ shortcomings. The proposed algorithm is based on MapReduce parallel programming framework of cloud computing, the matched pair, and finite automaton (FA) by using some efficient techniques such as preprocessing, constructing the efficient successor table and common subsequenceAtm, and looking for MLCS, and so forth. The theoretical analysis to the proposed algorithm shows that the time and space complexity are linear, that is, they are max{O(n),O(|Q|)} and O(∑i=1d|Si|+∑a∈Σ∏i=1d|Si′|a), respectively, which are superior to the leading parallel MLCS algorithms. Moreover, the simulation experiments of the proposed algorithm on some real DNA and amino acid sequence sample datasets are made, and their performance is compared with that of one of the current leading algorithms: FAST-LCS. The experimental results show that the proposed algorithm is very efficient and effective, and its performance is much better than that of FAST-LCS, especially for the cases of a large alphabet, a considerable number and a long average length of sequences. Meanwhile, experimental results also verify the correctness of our theoretical analysis.



---

*Source: 310328-2012-10-30.xml*