BACKGROUND
biological sequence  <cit>  can be represented as a sequence of symbols.
for instance, a protein  <cit>  is a sequence of  <dig> different letters , and dna sequences  can be represented as sequences of four letters a, c, g and t corresponding to the four sub-molecules forming dna.
when a new biosequence is found, we want to know what other sequences it is most similar to.
sequence comparison  <cit>  has been used successfully to establish the link between cancer-causing genes and a gene evolved in normal growth and development.
one way of detecting the similarity of two or more sequences is to find their lcs.
the lcs problem is to find a substring that is common to two or more given strings and is the longest one of such strings.
since the lcs problem is essentially a special case of the global sequence alignment, all the algorithms for the sequence alignment can be used to solve the lcs problem.
presented in  <dig>  the smith-waterman algorithm  <cit>  is a well known lcs algorithm which was evolved from the needleman-wunsch  <cit>  algorithm, and can guarantee the correctness.
aho and et al.
<cit>  gave a lower bound of o on time for the lcs problem using a decision tree model.
it is shown in  <cit>  that the problem can be solved in o time using o space by dynamic programming.
mayers and miller  <cit>  used the technique proposed by hirschberg  <cit>  to reduce the space complexity to o on the premise of the same time complexity.
to further reduce the computation time, some parallel algorithms  <cit>  have been proposed for different computational models.
for the crew-pram model, aggarwal  <cit>  and apostolico et al  <cit>  independently proposed an o time algorithm using mn/log m processors.
lu et al  <cit>  designed two parallel lcs algorithms, one uses mn/log m processors with a time complexity of o, and the other uses mn/ processors with a running time of o. for the crcw-pram model, apostolico et al  <cit>  gave an o2) time algorithm using mn/loglogm processors.
babu and saxena  <cit>  improved these algorithms for the crcw-pram model.
they designed an o algorithm with mn processors and an o time parallel algorithm.
many parallel lcs algorithms have also been proposed using systolic arrays.
robert et al  <cit>  proposed a parallel algorithm with n + 5m steps using m processing elements.
chang et al  <cit>  put forward an algorithm with 4n+2m steps using mn processing elements.
luce et al  <cit>  designed a systolic array with m/ <dig> processing elements and n+3m+q steps where q is the length of the lcs.
freschi and bogliolo  <cit>  addressed the problem of computing the lcs between run-length-encoded  strings.
their algorithm requires o steps on a systolic array of m+n processing elements, where m and n are the lengths of the original strings and m and n are the number of runs in their rle representation.
for the lcs problem of multiple sequences, the time complexity tends to grow very fast when the number of the sequences increases.
for instance, using the smith-waterman algorithm to solve the lcs for multiple sequences, the time complexity is , where n is the number of sequences, and ni is the length of the ith sequence.
it is not practicable when n is large.
some improvements have been made on the algorithm.
the msa program  <cit>  can process up to ten closely related sequences.
it is an implementation of the carrillo and lipman algorithm  <cit>  that identifies in advance the portions of the hyperspace not contributing to the solution and excludes them from the computation.
stoye described a new divide and conquer algorithm dca  <cit>  that extends the capability of msa.
recently, oma  <cit> , an iterative implementation of dca is proposed to speed up the dca strategy and reduce memory requirements.
based on feng and doolittle's algorithm  <cit> , clustal-w  <cit>  is one of the most widely used multiple sequence alignment software that can also be used for lcs computation.
RESULTS
in this paper, we present a fast algorithm named fast_lcs for efficient computation of lcs.
the algorithm first seeks the successors of the initial identical character pairs according to a successor table to obtain all the identical pairs and their levels.
then by tracing back from the identical character pair in the last level, it obtains the result of lcs.
the key technique of our algorithm is the use of several effective pruning operations.
in the process of generating the successors, pruning techniques can remove the identical pairs which can not generate the lcs so as to reduce the search space and accelerate the search speed.
the algorithm can be extended to find the lcs of multiple biosequences.
experimental results on the gene sequences of the tigr database, using an mpp parallel computer shenteng  <dig>  show that our algorithm can obtain the exact optimal results and is much faster than some other leading lcs algorithms.
CONCLUSIONS
in this paper, we have developed fast_lcs, one of the fastest parallel lcs algorithms on an mpp parallel computing model.
for two sequences x and y with lengths n and m, respectively, the memory complexity of fast_lcs is max{4*+4*, l}, where l is the number of identical character pairs.
the time complexity is o for sequential execution of the algorithm, and o|) for parallel execution, where |lcs| is the length of the lcs of x and y. the algorithm can be extended to solve the lcs for multiple biosequences.
for n sequences x <dig>  x <dig>  ..., xn, the time complexity is o for sequential execution, and o|), which is independent of the number of sequences, for parallel execution.
experimental results support our analysis by showing significant improvement of the proposed method over some other leading lcs algorithms.

 biological sequence can be represented as a sequence of symbols. for instance, a protein is a sequence of different letters, and dna sequences can be represented as sequences of four letters a, c, g and t corresponding to the four sub-molecules forming dna. when a new biosequence is found, we want to know what other sequences it is most similar to. sequence comparison has been used successfully to establish the link between cancer-causing genes and a gene evolved in normal growth and development. one way of detecting the similarity of two or more sequences is to find their lcs. the lcs problem is to find a substring that is common to two or more given strings and is the longest one of such strings. since the lcs problem is essentially a special case of the global sequence alignment, all the algorithms for the sequence alignment can be used to solve the lcs problem. presented in the smith-waterman algorithm is a well known lcs algorithm which was evolved from the needleman-wunsch algorithm, and can guarantee the correctness. aho and et al. gave a lower bound of o on time for the lcs problem using a decision tree model. it is shown in that the problem can be solved in o time using o space by dynamic programming. mayers and miller used the technique proposed by hirschberg to reduce the space complexity to o on the premise of the same time complexity. to further reduce the computation time, some parallel algorithms have been proposed for different computational models. for the crew-pram model, aggarwal and apostolico et al independently proposed an o time algorithm using mn/log m processors. lu et al designed two parallel lcs algorithms, one uses mn/log m processors with a time complexity of o, and the other uses mn/ processors with a running time of o. for the crcw-pram model, apostolico et al gave an o2) time algorithm using mn/loglogm processors. babu and saxena improved these algorithms for the crcw-pram model. they designed an o algorithm with mn processors and an o time parallel algorithm. many parallel lcs algorithms have also been proposed using systolic arrays. robert et al proposed a parallel algorithm with n + 5m steps using m processing elements. chang et al put forward an algorithm with 4n+2m steps using mn processing elements. luce et al designed a systolic array with m/ processing elements and n+3m+q steps where q is the length of the lcs. freschi and bogliolo addressed the problem of computing the lcs between run-length-encoded strings. their algorithm requires o steps on a systolic array of m+n processing elements, where m and n are the lengths of the original strings and m and n are the number of runs in their rle representation. for the lcs problem of multiple sequences, the time complexity tends to grow very fast when the number of the sequences increases. for instance, using the smith-waterman algorithm to solve the lcs for multiple sequences, the time complexity is, where n is the number of sequences, and ni is the length of the ith sequence. it is not practicable when n is large. some improvements have been made on the algorithm. the msa program can process up to ten closely related sequences. it is an implementation of the carrillo and lipman algorithm that identifies in advance the portions of the hyperspace not contributing to the solution and excludes them from the computation. stoye described a new divide and conquer algorithm dca that extends the capability of msa. recently, oma, an iterative implementation of dca is proposed to speed up the dca strategy and reduce memory requirements. based on feng and doolittle's algorithm, clustal-w is one of the most widely used multiple sequence alignment software that can also be used for lcs computation.  in this paper, we present a fast algorithm named fast_lcs for efficient computation of lcs. the algorithm first seeks the successors of the initial identical character pairs according to a successor table to obtain all the identical pairs and their levels. then by tracing back from the identical character pair in the last level, it obtains the result of lcs. the key technique of our algorithm is the use of several effective pruning operations. in the process of generating the successors, pruning techniques can remove the identical pairs which can not generate the lcs so as to reduce the search space and accelerate the search speed. the algorithm can be extended to find the lcs of multiple biosequences. experimental results on the gene sequences of the tigr database, using an mpp parallel computer shenteng show that our algorithm can obtain the exact optimal results and is much faster than some other leading lcs algorithms.  in this paper, we have developed fast_lcs, one of the fastest parallel lcs algorithms on an mpp parallel computing model. for two sequences x and y with lengths n and m, respectively, the memory complexity of fast_lcs is max{4*+4*, l}, where l is the number of identical character pairs. the time complexity is o for sequential execution of the algorithm, and o|) for parallel execution, where |lcs| is the length of the lcs of x and y. the algorithm can be extended to solve the lcs for multiple biosequences. for n sequences x x..., xn, the time complexity is o for sequential execution, and o|), which is independent of the number of sequences, for parallel execution. experimental results support our analysis by showing significant improvement of the proposed method over some other leading lcs algorithms. 
experimental results on gene sequences in the tigr database show that our algorithm is optimal and much more efficient than other leading lcs algorithms. experimental results support our analysis by showing significant improvement of the proposed method over other leading lcs algorithms. it then obtains the lcs by tracing back from the identical character pairs at the last level. for two sequences x and y with lengths n and m, respectively, the memory required is max{4*+4*, l}, where l is the number of identical character pairs. the time complexity is o for sequential execution, and o|) for parallel execution, where |lcs| is the length of the lcs of x and y. for n sequences x x..., xn, the time complexity is o for sequential execution, and o|) for parallel execution. searching for the longest common sequence of multiple biosequences is one of the most fundamental tasks in bioinformatics. we have developed one of the fastest parallel lcs algorithms on an mpp parallel computing model. the algorithm first constructs a novel successor table to obtain all the identical pairs and their levels. in this paper, we present a parallel algorithm named fast_lcs to speedup the computation for finding lcs. a fast parallel algorithm for lcs is presented.
 searching for the longest common sequence of multiple biosequences is one of the most fundamental tasks in bioinformatics. in this paper, we present a parallel algorithm named fast_lcs to speedup the computation for finding lcs.  a fast parallel algorithm for lcs is presented. the algorithm first constructs a novel successor table to obtain all the identical pairs and their levels. it then obtains the lcs by tracing back from the identical character pairs at the last level. effective pruning techniques are developed to significantly reduce the computational complexity. experimental results on gene sequences in the tigr database show that our algorithm is optimal and much more efficient than other leading lcs algorithms.  we have developed one of the fastest parallel lcs algorithms on an mpp parallel computing model. for two sequences x and y with lengths n and m, respectively, the memory required is max{4*+4*, l}, where l is the number of identical character pairs. the time complexity is o for sequential execution, and o|) for parallel execution, where |lcs| is the length of the lcs of x and y. for n sequences x x..., xn, the time complexity is o for sequential execution, and o|) for parallel execution. experimental results support our analysis by showing significant improvement of the proposed method over other leading lcs algorithms. june 20– symposium of computations in bioinformatics and bioscience in conjunction with the international multi-symposiums on computer and computational sciences hangzhou, china 