BACKGROUND
the problem of finding a shortest common supersequence  of a given set of sequences is a very important problem in computer science, especially in computational molecular biology.
the scs of a set of sequences can be stated as follows: given two sequences s = s1s <dig> ..sm and t = t1t <dig> ..tn, over an alphabet set Σ = {σ <dig>  σ <dig> ...,σq}, we say that s is the subsequence of t  if for every sj, there is  for some  <dig> ≤ i <dig> <i <dig> < ... <im ≤ n. given a finite set of sequences s = {s <dig>  s <dig> ...,sk}, a common supersequence of s is a sequence t such that t is a supersequence of every sequence sj  in s. then, a shortest common supersequence  of s is a supersequence of s that has minimum length.
in this paper, we shall assume that k is the number of sequences in s, n is the length of each sequence, and q = |Σ| is the size of the alphabet.
the scs problem has applications in many diverse areas, including data compression  <cit> , scheduling  <cit> , query optimization  <cit> , text comparison and analysis, and biological sequence comparisons and analysis  <cit> .
as a result, the scs problem has been very intensively researched  <cit> .
one basic result is that the scs of two sequences of length n can be computed using dynamic programming in o time and o space .
there are also several papers that reported improvements on the running time and space required for dynamic programming algorithms  <cit> .
for a fixed k, the dynamic programming algorithm can be extended to solve the scs problem for k sequences of length n in o time and space.
clearly, this algorithm is not practical for large k. the general scs problem on arbitrary k sequences of length n is well-known to be np-hard.
in fact, jiang and li  <cit>  showed that even the problem of finding a constant-ratio approximation solution is also np-hard.
a trivial algorithm, called alphabet  <cit>  gives an approximation ratio of q = |Σ|.
in practice, it is well known that heuristic algorithms produce results that are better than the alphabet algorithm.
many heuristic algorithms have been proposed for the general scs problem, including alphabet  <cit> , majority merge  <cit> , tournament  <cit> , greedy  <cit> , and reduce-expand  <cit> .
several heuristic algorithms were also proposed specifically for computing the scs of dna sequences .
these include min-height  <cit> , sum-height  <cit>  heuristics.
recently, we  <cit>  proposed look-ahead extensions of these heuristics, as well as a post-processing reduction procedure and studied the performances of these algorithms on dna sequences to be used for the synthesis of oligo-array.
this paper focuses on algorithms for solving large scs instances.
by large scs instances, we mean scs instances s in which
the sequences in s are long ,
there are many sequences , and
the alphabet set may be big .
large scs instances arise more frequently in the post-genome era in biological applications dealing with dna and protein sequences.
in this paper, we propose to solve large scs instances with our deposition and reduction algorithm .
the dr algorithm is based on the post processing algorithm that we have proposed on the scs problem for dna oligos  <cit> .
the dr algorithm is suitable for solving large scs instances – for example, scs instances with up to  <dig>  dna and protein sequences each of length  <dig>  we present experimental evaluation using simulated data and real dna and protein sequences to show that our dr algorithm outperforms the other heuristic algorithms for the scs problem on these large scs instances.
previous research of the scs problem
we now present a brief survey of several heuristic algorithms for the scs problem.
due to space limitation, we will focus only on algorithms that we have included in our comparative study.
let s be any instance of the scs problem and let csa be the supersequence of s computed by a heuristic algorithm a. let opt denote an optimal solution for the instance s. then, we say that a has an approximation ratio of λ if |csa|/|opt| ≤ λ for all instances s.
alphabet algorithm  <cit>
the alphabet algorithm is a very simple algorithm.
let s be a set of sequences of maximum length n over the alphabet Σ = {σ <dig>  σ <dig> ...,σq}, then the alphabet algorithm outputs a common supersequence of n. the alphabet algorithm has an approximation ratio of q = |Σ|.
the time complexity of the alphabet algorithm is o. there have also been modifications of the alphabet algorithm that uses information from s to "remove" redundant characters in n. these methods improve the performance in practice, but not in the worst case approximation ratio of q.
majority-merge algorithm  <cit>
the majority-merge algorithm  is a simple, greedy heuristic algorithm.
suppose we analyze every sequence from left to right, the frontier is defined as the rightmost characters to be analyzed.
initially, the supersequence cs is empty.
at each step, let s be the majority among the "frontier" characters of the remaining portions of the sequences in s. set cs = cs||s  and delete the "frontier" s characters from sequences in s. repeat until no sequences are left.
this algorithm is the same as the sum height algorithm  proposed in  <cit> .
this algorithm does not have any worst-case approximation ratio, but performs very well in practice.
the time complexity of the majority-merge algorithm is o.
greedy and tournament algorithms  <cit>
the greedy algorithm  and tournament algorithm  studied in  <cit>  are two variations of an iterative scheme based on combining "best" sequence pairs.
given any pair of sequences, si and sj, an optimal supersequence of the pair, denoted by scs, can be computed in o using dynamic programming.
the greedy algorithm first chooses the "best" sequence pair – the pair that gives the shortest scs.
without loss of generality, we assume that these two sequences are s <dig> and s <dig>  the algorithm then replaces the two sequences s <dig> and s <dig> by their supersequence, scs.
the algorithm proceeds recursively.
thus, we can express it as follows:
greedy = greedy, s <dig> ...,sk).
the tournament algorithm is similar to the greedy algorithm.
it builds a "tournament" based on finding multiple best pairs at each round and can be expressed schematically as follows:
tournament = tournament, scs,...,scs).
both greedy and tournament algorithms have o time complexity and o space complexity.
unfortunately, it was shown in  <cit>  that both greedy and tournament do not have approximation ratios.
reduce-expand algorithm  <cit>
the reduce-expand algorithm  is based on reducing sequences to basic sequences, which are sequences that have no adjacent characters of the same alphabet.
for example, sequence "aacgg" can be reduced to basic sequence of "ag".
the expand process tries to add characters into the common subsequence of the sequences, while preserving the common subsequence property.
using a process of reduce, auxiliary set and expand, this algorithm can produce short scs on binary sequences as well as datasets with few sequences and more alphabets.
the re algorithm has an approximation ratio of q = |Σ| and has time complexity o and space complexity o, where α ≥  <dig> is a constant integer.
it was shown in  <cit>  that re performs well on longer sequences  with larger alphabets.
however, the experimental studies were confined to datasets with relatively few sequences .
for large scs instances, the space and time requirements of re may be a limiting factor.
we next survey heuristic algorithms  <cit>  that were designed specifically to target the scs of dna sequences – to be used for synthesis of dna microarrays and oligo-arrays.
to describe these methods, we adopt the notations used in  <cit> , and used examples in dna sequences.
an example of sequence deposition is shown in figure  <dig>  after t cycles, a partial sequence has been synthesized.
the height of each partially constructed sequence is defined as the number of bases in it.
indication of how much work that has been accomplished after t cycles is measured in terms of  the min-height  – the height of the shortest partially constructed sequences after t cycles, or  the sum-height  – the sum of the heights of the partially constructed sequences.
min-height  <cit>
the min-height  greedy method, denoted here by mh, selects a character that will extend the shortest partially constructed oligo by one base .
when there is a tie, we randomly pick one such character.
sum-height  <cit>
the sum-height  greedy method, denoted by sh, selects a character that will result in the largest increase in the sum-height.
this method is the same as the majority merge  algorithm.
again, ties are broken randomly.
both mh and sh are very fast algorithms, with time complexity of o time.
in general, they work well for dna sequences.
look-ahead extensions of sh and mh
a natural way to improve the fast greedy algorithms mh and sh is to apply a "look-ahead" strategy to it  <cit> .
this strategy looks at a number of steps ahead before deciding which character is the best to be added.
more specifically, choose two integers m and l such that l ≤ m. then, the look-ahead extension of the sh method works as follows:  examine all possible partial sequences that can be generated in m cycles;  for each such generated partial sequences, compute the resulting sum height; and  select the partial sequence that will result in the largest increase of sum-height in m cycles.
then, we extend the chosen sequence by l  characters.
gives the potential of obtaining even better increase in the sum-height after m cycles.)
here we break the tie arbitrarily.
this look ahead algorithm is called the -look-ahead sh, and is abbreviated to -la-sh.
the look-ahead extension of mh is defined in a similar fashion, and is denoted by -la-mh.
it is easy to see that an increase in m naturally leads to a shorter scs, but at a cost of a substantial increase in computing time.
experimentation done in  <cit>  indicated that la-sh gives the best performance and that -la-sh gives the best trade-off between running time and quality of the scs solution.
look-ahead post processing algorithm  <cit>
finally, we recently proposed a look-ahead post processing  algorithm to solve the scs problem on many dna sequences that produce very good results for the case when the number of sequences k is large  and sequence length n is relatively small .
the lap algorithm outperforms alphabet, sh, and mh heuristics on these scs instances.
hubbell-morris-winkler algorithm  <cit>
the hubbell-morris-winkler algorithm is another heuristic algorithm specifically designed for scs of dna oligos .
the method consists of two key steps.
first, it finds a shortest periodical strategy  corresponding to the following string:   ... , where x, y, z, u denote the four different characters in some order.
second, examine each character in a cycle from the first to the last and remove the character if either  it is not needed by any oligo, or  it can be added in a later cycle.
hubbell-morris-winkler algorithm has comparable performance compared to our lap algorithm on dna sequences.
however, the algorithm is only suitable for sequences small alphabet size q such as dna sequences.
for protein sequences , there are  <dig> periodical strategies and so the hubbell-morris-winkler algorithm is not practical any more.
other algorithms
other scs algorithms have also been proposed  <cit> , but were not included in this study because they involve meta-heuristic search  and have very long running times.
thus, they are not practical for the large scs instances considered in this paper.
performance ratio
to compare the performances of different algorithms across different instances of different sizes, we define the notion of performance ratio.
for any instance s, the performance ratio, ra, of algorithm a on instance s is defined by ra = |csa|/|opt|, where opt is an optimal scs solution to the instance s.
however, |opt| is unknown – it is not feasible to compute |opt| since the scs problem is np-hard.
luckily, it is possible to compute a lower bound for |opt|.
we choose a small sample set, ss, of representative sequences in s and use an exact dynamic programming algorithm to compute opt, the shortest common supersequence of the sample set ss.
clearly, |opt| is a lower bound on the optimum length, namely, |opt| ≤ |opt|.
then the performance ratio ra can also be upper bounded by the estimate r'a = |csa|/|opt|.
we shall use the estimated performance ratio bounds as a "metric" for comparing different algorithms later in this paper.
the gap between |opt| and the computed lower bound, |opt| depends on how the sample set ss is chosen and also on its size.
however, a large ss will render the computation infeasible.
for dna sequences, we use the sample set ss = {ssa, ssc, ssg, sst} of  <dig> representative sequences from s, where each representative sequence ssa  is a sequence in s that has the largest number of a's .
then dynamic programming is applied on {s <dig>  s <dig> ...sq} to obtain a lower bound of the scs length.
for protein sequences with q =  <dig>  we choose only top few  such representative sequences in the sample set ss.
method
since biological datasets usually contain many long sequences , it is important to devise an effective algorithm that works well on large scs instances .
among the existing heuristic algorithms, several of them  perform well on scs instances where there are few long sequences .
several heuristic algorithms  perform well on scs instances with many short sequences .
however, relatively few research studies have been carried out to see how they perform on large scs instances dealing with many long sequences .
in fact, barone et al.
had in  <cit> , raised the question on "how to design efficient  heuristic algorithm on many long sequences".
in our recent work  <cit> , we have compared the performances of several algorithms -la-sh, and lap) on scs instances where k is large, but n is relatively small.
the good performance of our lap algorithm  <cit> , indicates that the post processing approach may also be effective on large scs instances .
this paper discusses how we modify the lap algorithm to solve large scs instances.
our dr algorithm for large scs instances
in the deposition and reduction algorithm that we proposed, there are two processes: in the deposition process, we first generate a template pool – a small set of scs templates .
each template is a common supersequence of the scs instance s. the reduction process shortens these templates by attempting to remove some characters while preserving the common supersequence property.
this uses the post processing procedure introduced in  <cit> .
deposition process
for the deposition process, we use two algorithms to produce candidate templates that will be included in the template pool.
clearly, the performance of the algorithm is dependent on obtaining good scs templates.
based on results from our previous study  <cit> , we have selected -la-sh as one of the algorithms used to generate one of the templates.
another template used was that generated by alphabet .
reduction process
in the reduction process, we apply a reduction procedure to each scs template in the template pool to obtain a shorter scs.
finally, the shortest result obtained after this reduction process is selected as the final output of the algorithm.
the reduction procedure we use is just a simple extension of the post-processing procedure in  <cit> .
we give a brief description here.
we are given a scs template s = s <cit> s <cit> ...s, with m characters .
the following approach, using s as a template and a method a, seeks to reduce the number of characters in s. the detailed algorithm is given in figure  <dig>
in the current implementation of our deposition and reduction algorithm , we have included the template generated by the alphabet algorithm.
thus, our dr algorithm also has an approximation ratio of q = |Σ|.
however, in practice, our experiment show the results from the -la-sh template is much better than those obtained from alphabet and the performance ratios of the dr algorithm is much lower than q.
the time complexity of the deposition process is o, the time complexity of the reduction process is o, so the total time complexity of the deposition and reduction algorithm is o. this is larger than that of alphabet algorithm, but smaller than greedy algorithm and tournament algorithm where q is not very large and k is large.
it is also smaller than that of the reduce-expand algorithm, especially when n is large.
the space complexity of the deposition and reduction algorithm is o.
RESULTS
our post process algorithm is written in java and perl.
the experiments are performed on a pc with  <dig>  ghz cpu and  <dig>  gb memory, running on a linux operating system.
we have selected alphabet   <cit> , reduce-expand   <cit> , tournament , greedy   <cit>  and majority merge   <cit>  algorithms, as well as lower bound  for comparison with our deposition and reduction  algorithm on large scs instances.
we also used abbreviations defined above for the different heuristic algorithms.
we note here that the re algorithm was not included in the comparative study of large scs instances as the re algorithm took too long to run on these large scs instances.
instead, we compare the re algorithm with our dr algorithm directly on smaller scs instances in the subsection on "comparison with reduce-expand algorithm".
for the large scs instances, we use both simulated sequences as well as real  sequences.
it is easy to see that results on datasets with sequences of different lengths are similar to those results on datasets with sequences of same lengths.
therefore, in this study, we have only used simulated sequences of same length in the dataset, and also truncated real sequence to same lengths in each datasets.
in the tables of experimental results below, k denotes the number of sequences, and n denotes the length of the sequence.
for dna sequences, the size of alphabet q =  <dig>  while for protein sequences q =  <dig>
results on simulated sequences
we first carry out comparative study on simulated dna sequences.
for each value of k =  <dig>   <dig>   <dig>   <dig>  and n =  <dig>   <dig>  we generated  <dig> random datasets of dna sequences.
these datasets are shown in tables  <dig> and  <dig> where each row represents the composite result for the  <dig> instances.
for each row, we also compute the average lower bound  over the  <dig> instances.
then, each algorithm, a, is run on these  <dig> instances to get an average  of |csa|, the length of the scs.
the estimated performance ratios of the different algorithms  are obtained by dividing the average scs lengths by the lower bound lb.
as mentioned earlier, these are upper bounds on the true performance ratios of the algorithms.
in table  <dig>  we first study the effect of deposition process and reduction process in our dr algorithm.
to this end, we define csd and csr to be the common supersequences obtained after the deposition and reduction process, respectively.
from table  <dig>  we observed that both the deposition and the reduction processes are effective.
the deposition process always output templates with |templated| /|opt| less than  <dig>  for both long  and short  sequences.
in the following tables, we will see that this is much better than results of alphabet, indicating the superiority of -la-sh template.
the reduction process can further reduce the lengths of the results by between  <dig> to  <dig> characters for n =  <dig>  and by about  <dig> characters for n =  <dig>  and the performance ratios are correspondingly reduced.
the standard deviations for the results of both deposition and reduction processes are not big, indication that both the deposition process and the reduction process give stable results.
in table  <dig>  we then compared the various heuristic algorithms – alphabet, tournament, greedy, majority merge  with our dr algorithm on these simulated dna datasets.
to assist the comparison, we have also included the lower bound , and the average estimated performance ratios.
the results in table  <dig> show very clearly that for the datasets with large k and n, the dr algorithm consistently gives the best results, followed quite closely by mm, while algorithms tour and grdy are quite a bit worse.
generally, we observe that the length of the scs obtained increases with the number of sequences, which is to be expected.
the performances of the algorithms on medium length sequences  also differ slightly from those for long sequences .
for n =  <dig>  our dr algorithm produces results that are, on average, shorter than those of mm by  <dig>  characters, by  <dig>  characters than those of grdy, and by  <dig> characters than those of tour.
for long sequences , the difference are more pronounced, by  <dig>  characters for mm, by  <dig> characters for grdy, and by  <dig> characters for tour.
similar to the results observed in  <cit> , the performance ratios obtained by all the algorithms are quite a bit below the worst-case ratio of  <dig> for the trivial alphabet algorithm.
the standard deviation results in table  <dig> also show that dr algorithm is relatively stable – more stable than grdy and tour, but not as stable the mm algorithm.
we have not done a similar comparison on simulated protein sequences, but we expect that the relative performances of these algorithms on random protein sequences would be similar to those for random dna sequences.
in the next section, we show results on real dna and protein sequences.
results on real biological sequences
in this section, we compared the algorithms alphabet and mm with our dr on datasets obtained from real dna and protein sequences.
for this study, we have to exclude the grdy and tour algorithms since their performances are much worse than mm or dr, and they are also very time-consuming on these datasets.
for this experimental comparison, we have randomly selected dna sequences from the ncbi viral genomes  <cit> .
these dna sequences are truncated so that they have lengths  of  <dig> and  <dig> and combined to obtained many datasets that are grouped into four cases  with k =  <dig> and  <dig>  and  <dig> randomly selected datasets for each setting, as shown in table  <dig>  the protein sequences  are from swissprot  <cit>  and these have been truncated to length  <dig> and we have used k =  <dig>   <dig>  and  <dig> to truncate datasets, and  <dig> randomly selected datasets for each setting.
these datasets are grouped into three cases  as shown in table  <dig>  both real dna and protein sequences datasets are available as additional supplemental materials.
the comparison results for mm and dr algorithms on these selected dna and protein sequences are shown in table  <dig>  the results for real dna sequences are similar to those for simulated dna sequences.
again, the results clearly show that dr consistently outperform the mm algorithm for both type of sequences.
the performance ratio |csdr|/|opt| of dr algorithm is about  <dig>  for dna sequences with length  <dig> and  <dig>  and  <dig> ~ <dig>  for protein sequences with length  <dig>  these are much less than the approximation ratios.
we also observe that the length of the scs obtained increases with the number of sequences.
comparing table  <dig> with table  <dig>  we also observed that the performance ratios for mm and dr are generally a little bigger for real dna sequences as compared to simulated dna sequences for similar values of k and n. this may be attributed to the fact that the real dna sequences are selected from different viral genomes and thus, there is high variance in the gc contents and this may have resulted in longer scs.
whereas, in the simulated dna sequences, the gc content is predefined for each of the simulated dna sequences datasets and this may have resulted in the shorter scs obtained by the algorithms.
this observation is also consistent with results in  <cit> .
the results for protein sequences show a similar trend as those for dna sequences.
note that the approximation ratio for the alphabet algorithm is  <dig> for protein sequences.
our results show that for dr on protein sequences with n =  <dig>  the performance ratio is smaller than those for mm.
the difference in the performance ratios of dr and mm is larger for protein sequences that have a larger alphabet.
in terms of the length of the scs result, dr obtains scs results that are between  <dig> to  <dig> characters shorter compared to those obtained by mm.
the standard deviations observed in table  <dig> for dna and protein sequences are relatively small, again indicating that both mm and dr algorithms give relatively stable performance.
comparison with reduce-expand algorithm
the reduce-expand  algorithm  <cit>  is currently one of the best algorithms for the general scs problem for small scs instances.
because of the high running time of the re algorithm, we have only compared re with our dr algorithm on simulated datasets with relatively few, short dna sequences , as well as small datasets of real dna and protein sequences.
the results on simulated datasets are shown in table  <dig>
the results in table  <dig> indicate that dr is only comparable to  re in the lengths of the results when there are only  <dig> sequences, but outperform re in the lengths of the results when the number of sequences is over  <dig>  the more sequences, and the longer the sequences, the larger differences between the length of the results of dr and re.
especially for longer  sequences, the results of dr can be about  <dig> to  <dig> characters shorter than the results of re.
we have also compared the algorithms alphabet and re with our dr on datasets obtained from real dna and protein sequences.
the sequences in datasets  are shorter from those in table  <dig>  and the results are shown in table  <dig>
the results on real dna and protein sequences are consistent with the results on simulated sequences.
the dr algorithm can outperform the re algorithm by about  <dig> characters for dna sequences of length  <dig>  the scs results of the dr algorithm are also shorter than the results of the re algorithm by more than  <dig> characters on protein sequences.
the more sequences, and the longer the sequences, the larger differences between the length of the results of the dr and re algorithm.
computational efficiency
our deposition and reduction  algorithm has time complexity of o and space complexity of o. in our experiments, the dr algorithm is very fast, even for large scs datasets – for example, for  <dig> sequences of length  <dig> each, it take an average of 5– <dig> minutes per instance.
in comparison to existing algorithms, it is slower than majority merge, min height , but it is much faster than greedy and tournament algorithms .
the dr algorithm is also much faster than the reduce-expand algorithm .
for a simulated dna dataset with  <dig> sequences each of length  <dig>  the dr algorithm can get result in less than  <dig> seconds, while the reduce-expand algorithm needs more than  <dig> minutes.
the actual computer memory used by the dr algorithm is about  <dig> m for some of our very large datasets; majority merge needs about  <dig> m for these same datasets.
the software is available upon request, and the web services portal will be available soon.
CONCLUSIONS
in this paper, we have proposed a deposition and reduction  algorithm for solving large scs instances.
the dr algorithm is composed of the deposition process to generate good templates, and the reduction process to reduce templates from template pool to get short result.
these processes are shown to be powerful for the scs problem.
we have compared the performance of our dr algorithm with some of the best heuristic algorithms on different sequences datasets, especially on many long sequences.
the dr algorithm has superior performance than alphabet, tournament, greedy and majority merge algorithms in practice, especially on many long sequences.
it also outperforms the reduce-expand algorithm for sequences of length 50~ <dig>  the dr algorithm is also very efficient in time and space, which partially answer the question that barone et al.
raised  <cit>  about how to design efficient  heuristic algorithm on many long sequences.
the deposition and reduction algorithm is an extension of our previous study for scs problem on dna oligos  <cit> .
to our best knowledge, our deposition and reduction is one of the best heuristic algorithms  for the scs problem on biological sequences such as the dna and protein sequences, especially for datasets with many long sequences.
we believe that the use of the deposition and reduction algorithm can facilitate the biological sequencing process for bioinformatics researches.
there are many other post process strategies for the scs problem, such as better look ahead strategies, which may lead to better performance.
we are currently trying to further analyze these strategies for scs problems by comparing the results of different strategies.
as a general computational framework, this deposition and reduction algorithm can also be applied on more general applications such as text comparison and compression, query optimization and scheduling.
we will also work on these more general problems in the future.
supplementary material
additional file 1
real dna sequences dna sequences are obtained from ncbi viral genomes, accessed on 01/01/ <dig>  .
sequences are randomly selected from different genome sequences.
the specific length and number of sequences are specified for each dataset.
there are  <dig> randomly selected datasets.
file name indicate the number of sequences, sequence length, and dataset number.
for example, file name "dna_n100_k500_5" indicate that it is dna sequences dataset, with  <dig> sequences, each truncated to length of  <dig>  and this is number  <dig> datasets for this setting.
each sequence is represented as a row in the dataset file.
click here for file
additional file 2
real protein sequences protein sequences are obtained from swiss-prot release  <dig>  of 04-jan- <dig>  .
sequences are randomly selected from different protein sequences.
the specific length and number of sequences are specified for each protein dataset.
there are  <dig> randomly selected datasets.
file name indicate the number of sequences, sequence length, and dataset number.
for example, file name "protein_n100_k500_5" indicate that it is protein sequences dataset, with  <dig> sequences, each truncated to length of  <dig>  and this is number  <dig> datasets for this setting.
each sequence is represented as a row in the data file.
click here for file
acknowledgements
we thank anonymous reviewers for valuable comments on the paper.
this work was partially supported by the national university of singapore under grant r252-000-199- <dig>
this article has been published as part of bmc bioinformatics volume  <dig>  supplement  <dig>  2006: symposium of computations in bioinformatics and bioscience .
the full contents of the supplement are available online at .
figures and tables
sequences
length of cs
k
n
lb
r'
d
r'
r
each row of the table represents  <dig> randomly generated instances.
for each row, we list the average value for lb , |csd|, and |csr| , their standard deviations , and the estimated performance ratios r'd and r'r
sequences
length of cs
k
n
lb
alpha
ratio
tour
ratio
grdy
ratio
mm
ratio
dr
ratio
the average and standard deviation  over  <dig> randomly generated instances are given.
the estimated performance ratios are also given for each algorithm.
sequences
length of cs
k
n
lb
alpha
ratio
mm
ratio
dr
ratio
dna sequences
protein sequences
the average and standard deviation  are given.
the estimated performance ratios are also given for each algorithm.
sequences
length of scs
k
n
alpha
re
dr
in each cell, the average and standard deviation  over  <dig> randomly generated instances are given.
k
n
alpha
re
dr
dna
protein
in each cell, the average and standard deviation  over  <dig> randomly generated instances are given.

 the problem of finding a shortest common supersequence of a given set of sequences is a very important problem in computer science, especially in computational molecular biology. the scs of a set of sequences can be stated as follows: given two sequences s = s1s..sm and t = t1t..tn, over an alphabet set Σ = {σ σ...,σq}, we say that s is the subsequence of t if for every sj, there is for some ≤ i <i <... <im ≤ n. given a finite set of sequences s = {s s...,sk}, a common supersequence of s is a sequence t such that t is a supersequence of every sequence sj in s. then, a shortest common supersequence of s is a supersequence of s that has minimum length. in this paper, we shall assume that k is the number of sequences in s, n is the length of each sequence, and q = |Σ| is the size of the alphabet. the scs problem has applications in many diverse areas, including data compression, scheduling, query optimization, text comparison and analysis, and biological sequence comparisons and analysis. as a result, the scs problem has been very intensively researched. one basic result is that the scs of two sequences of length n can be computed using dynamic programming in o time and o space. there are also several papers that reported improvements on the running time and space required for dynamic programming algorithms. for a fixed k, the dynamic programming algorithm can be extended to solve the scs problem for k sequences of length n in o time and space. clearly, this algorithm is not practical for large k. the general scs problem on arbitrary k sequences of length n is well-known to be np-hard. in fact, jiang and li showed that even the problem of finding a constant-ratio approximation solution is also np-hard. a trivial algorithm, called alphabet gives an approximation ratio of q = |Σ|. in practice, it is well known that heuristic algorithms produce results that are better than the alphabet algorithm. many heuristic algorithms have been proposed for the general scs problem, including alphabet, majority merge, tournament, greedy, and reduce-expand. several heuristic algorithms were also proposed specifically for computing the scs of dna sequences. these include min-height, sum-height heuristics. recently, we proposed look-ahead extensions of these heuristics, as well as a post-processing reduction procedure and studied the performances of these algorithms on dna sequences to be used for the synthesis of oligo-array. this paper focuses on algorithms for solving large scs instances. by large scs instances, we mean scs instances s in which the sequences in s are long, there are many sequences, and the alphabet set may be big. large scs instances arise more frequently in the post-genome era in biological applications dealing with dna and protein sequences. in this paper, we propose to solve large scs instances with our deposition and reduction algorithm. the dr algorithm is based on the post processing algorithm that we have proposed on the scs problem for dna oligos. the dr algorithm is suitable for solving large scs instances – for example, scs instances with up to dna and protein sequences each of length we present experimental evaluation using simulated data and real dna and protein sequences to show that our dr algorithm outperforms the other heuristic algorithms for the scs problem on these large scs instances. previous research of the scs problem we now present a brief survey of several heuristic algorithms for the scs problem. due to space limitation, we will focus only on algorithms that we have included in our comparative study. let s be any instance of the scs problem and let csa be the supersequence of s computed by a heuristic algorithm a. let opt denote an optimal solution for the instance s. then, we say that a has an approximation ratio of λ if |csa|/|opt| ≤ λ for all instances s. alphabet algorithm the alphabet algorithm is a very simple algorithm. let s be a set of sequences of maximum length n over the alphabet Σ = {σ σ...,σq}, then the alphabet algorithm outputs a common supersequence of n. the alphabet algorithm has an approximation ratio of q = |Σ|. the time complexity of the alphabet algorithm is o. there have also been modifications of the alphabet algorithm that uses information from s to "remove" redundant characters in n. these methods improve the performance in practice, but not in the worst case approximation ratio of q. majority-merge algorithm the majority-merge algorithm is a simple, greedy heuristic algorithm. suppose we analyze every sequence from left to right, the frontier is defined as the rightmost characters to be analyzed. initially, the supersequence cs is empty. at each step, let s be the majority among the "frontier" characters of the remaining portions of the sequences in s. set cs = cs||s and delete the "frontier" s characters from sequences in s. repeat until no sequences are left. this algorithm is the same as the sum height algorithm proposed in. this algorithm does not have any worst-case approximation ratio, but performs very well in practice. the time complexity of the majority-merge algorithm is o. greedy and tournament algorithms the greedy algorithm and tournament algorithm studied in are two variations of an iterative scheme based on combining "best" sequence pairs. given any pair of sequences, si and sj, an optimal supersequence of the pair, denoted by scs, can be computed in o using dynamic programming. the greedy algorithm first chooses the "best" sequence pair – the pair that gives the shortest scs. without loss of generality, we assume that these two sequences are s and s the algorithm then replaces the two sequences s and s by their supersequence, scs. the algorithm proceeds recursively. thus, we can express it as follows: greedy = greedy, s...,sk). the tournament algorithm is similar to the greedy algorithm. it builds a "tournament" based on finding multiple best pairs at each round and can be expressed schematically as follows: tournament = tournament, scs,...,scs). both greedy and tournament algorithms have o time complexity and o space complexity. unfortunately, it was shown in that both greedy and tournament do not have approximation ratios. reduce-expand algorithm the reduce-expand algorithm is based on reducing sequences to basic sequences, which are sequences that have no adjacent characters of the same alphabet. for example, sequence "aacgg" can be reduced to basic sequence of "ag". the expand process tries to add characters into the common subsequence of the sequences, while preserving the common subsequence property. using a process of reduce, auxiliary set and expand, this algorithm can produce short scs on binary sequences as well as datasets with few sequences and more alphabets. the re algorithm has an approximation ratio of q = |Σ| and has time complexity o and space complexity o, where α ≥ is a constant integer. it was shown in that re performs well on longer sequences with larger alphabets. however, the experimental studies were confined to datasets with relatively few sequences. for large scs instances, the space and time requirements of re may be a limiting factor. we next survey heuristic algorithms that were designed specifically to target the scs of dna sequences – to be used for synthesis of dna microarrays and oligo-arrays. to describe these methods, we adopt the notations used in, and used examples in dna sequences. an example of sequence deposition is shown in figure after t cycles, a partial sequence has been synthesized. the height of each partially constructed sequence is defined as the number of bases in it. indication of how much work that has been accomplished after t cycles is measured in terms of the min-height – the height of the shortest partially constructed sequences after t cycles, or the sum-height – the sum of the heights of the partially constructed sequences. min-height the min-height greedy method, denoted here by mh, selects a character that will extend the shortest partially constructed oligo by one base. when there is a tie, we randomly pick one such character. sum-height the sum-height greedy method, denoted by sh, selects a character that will result in the largest increase in the sum-height. this method is the same as the majority merge algorithm. again, ties are broken randomly. both mh and sh are very fast algorithms, with time complexity of o time. in general, they work well for dna sequences. look-ahead extensions of sh and mh a natural way to improve the fast greedy algorithms mh and sh is to apply a "look-ahead" strategy to it. this strategy looks at a number of steps ahead before deciding which character is the best to be added. more specifically, choose two integers m and l such that l ≤ m. then, the look-ahead extension of the sh method works as follows: examine all possible partial sequences that can be generated in m cycles; for each such generated partial sequences, compute the resulting sum height; and select the partial sequence that will result in the largest increase of sum-height in m cycles. then, we extend the chosen sequence by l characters. gives the potential of obtaining even better increase in the sum-height after m cycles.) here we break the tie arbitrarily. this look ahead algorithm is called the -look-ahead sh, and is abbreviated to -la-sh. the look-ahead extension of mh is defined in a similar fashion, and is denoted by -la-mh. it is easy to see that an increase in m naturally leads to a shorter scs, but at a cost of a substantial increase in computing time. experimentation done in indicated that la-sh gives the best performance and that -la-sh gives the best trade-off between running time and quality of the scs solution. look-ahead post processing algorithm finally, we recently proposed a look-ahead post processing algorithm to solve the scs problem on many dna sequences that produce very good results for the case when the number of sequences k is large and sequence length n is relatively small. the lap algorithm outperforms alphabet, sh, and mh heuristics on these scs instances. hubbell-morris-winkler algorithm the hubbell-morris-winkler algorithm is another heuristic algorithm specifically designed for scs of dna oligos. the method consists of two key steps. first, it finds a shortest periodical strategy corresponding to the following string:..., where x, y, z, u denote the four different characters in some order. second, examine each character in a cycle from the first to the last and remove the character if either it is not needed by any oligo, or it can be added in a later cycle. hubbell-morris-winkler algorithm has comparable performance compared to our lap algorithm on dna sequences. however, the algorithm is only suitable for sequences small alphabet size q such as dna sequences. for protein sequences, there are periodical strategies and so the hubbell-morris-winkler algorithm is not practical any more. other algorithms other scs algorithms have also been proposed, but were not included in this study because they involve meta-heuristic search and have very long running times. thus, they are not practical for the large scs instances considered in this paper. performance ratio to compare the performances of different algorithms across different instances of different sizes, we define the notion of performance ratio. for any instance s, the performance ratio, ra, of algorithm a on instance s is defined by ra = |csa|/|opt|, where opt is an optimal scs solution to the instance s. however, |opt| is unknown – it is not feasible to compute |opt| since the scs problem is np-hard. luckily, it is possible to compute a lower bound for |opt|. we choose a small sample set, ss, of representative sequences in s and use an exact dynamic programming algorithm to compute opt, the shortest common supersequence of the sample set ss. clearly, |opt| is a lower bound on the optimum length, namely, |opt| ≤ |opt|. then the performance ratio ra can also be upper bounded by the estimate r'a = |csa|/|opt|. we shall use the estimated performance ratio bounds as a "metric" for comparing different algorithms later in this paper. the gap between |opt| and the computed lower bound, |opt| depends on how the sample set ss is chosen and also on its size. however, a large ss will render the computation infeasible. for dna sequences, we use the sample set ss = {ssa, ssc, ssg, sst} of representative sequences from s, where each representative sequence ssa is a sequence in s that has the largest number of a's. then dynamic programming is applied on {s s...sq} to obtain a lower bound of the scs length. for protein sequences with q = we choose only top few such representative sequences in the sample set ss. method since biological datasets usually contain many long sequences, it is important to devise an effective algorithm that works well on large scs instances. among the existing heuristic algorithms, several of them perform well on scs instances where there are few long sequences. several heuristic algorithms perform well on scs instances with many short sequences. however, relatively few research studies have been carried out to see how they perform on large scs instances dealing with many long sequences. in fact, barone et al. had in, raised the question on "how to design efficient heuristic algorithm on many long sequences". in our recent work, we have compared the performances of several algorithms -la-sh, and lap) on scs instances where k is large, but n is relatively small. the good performance of our lap algorithm, indicates that the post processing approach may also be effective on large scs instances. this paper discusses how we modify the lap algorithm to solve large scs instances. our dr algorithm for large scs instances in the deposition and reduction algorithm that we proposed, there are two processes: in the deposition process, we first generate a template pool – a small set of scs templates. each template is a common supersequence of the scs instance s. the reduction process shortens these templates by attempting to remove some characters while preserving the common supersequence property. this uses the post processing procedure introduced in. deposition process for the deposition process, we use two algorithms to produce candidate templates that will be included in the template pool. clearly, the performance of the algorithm is dependent on obtaining good scs templates. based on results from our previous study, we have selected -la-sh as one of the algorithms used to generate one of the templates. another template used was that generated by alphabet. reduction process in the reduction process, we apply a reduction procedure to each scs template in the template pool to obtain a shorter scs. finally, the shortest result obtained after this reduction process is selected as the final output of the algorithm. the reduction procedure we use is just a simple extension of the post-processing procedure in. we give a brief description here. we are given a scs template s = s s...s, with m characters. the following approach, using s as a template and a method a, seeks to reduce the number of characters in s. the detailed algorithm is given in figure in the current implementation of our deposition and reduction algorithm, we have included the template generated by the alphabet algorithm. thus, our dr algorithm also has an approximation ratio of q = |Σ|. however, in practice, our experiment show the results from the -la-sh template is much better than those obtained from alphabet and the performance ratios of the dr algorithm is much lower than q. the time complexity of the deposition process is o, the time complexity of the reduction process is o, so the total time complexity of the deposition and reduction algorithm is o. this is larger than that of alphabet algorithm, but smaller than greedy algorithm and tournament algorithm where q is not very large and k is large. it is also smaller than that of the reduce-expand algorithm, especially when n is large. the space complexity of the deposition and reduction algorithm is o.  our post process algorithm is written in java and perl. the experiments are performed on a pc with ghz cpu and gb memory, running on a linux operating system. we have selected alphabet, reduce-expand, tournament, greedy and majority merge algorithms, as well as lower bound for comparison with our deposition and reduction algorithm on large scs instances. we also used abbreviations defined above for the different heuristic algorithms. we note here that the re algorithm was not included in the comparative study of large scs instances as the re algorithm took too long to run on these large scs instances. instead, we compare the re algorithm with our dr algorithm directly on smaller scs instances in the subsection on "comparison with reduce-expand algorithm". for the large scs instances, we use both simulated sequences as well as real sequences. it is easy to see that results on datasets with sequences of different lengths are similar to those results on datasets with sequences of same lengths. therefore, in this study, we have only used simulated sequences of same length in the dataset, and also truncated real sequence to same lengths in each datasets. in the tables of experimental results below, k denotes the number of sequences, and n denotes the length of the sequence. for dna sequences, the size of alphabet q = while for protein sequences q = results on simulated sequences we first carry out comparative study on simulated dna sequences. for each value of k = and n = we generated random datasets of dna sequences. these datasets are shown in tables and where each row represents the composite result for the instances. for each row, we also compute the average lower bound over the instances. then, each algorithm, a, is run on these instances to get an average of |csa|, the length of the scs. the estimated performance ratios of the different algorithms are obtained by dividing the average scs lengths by the lower bound lb. as mentioned earlier, these are upper bounds on the true performance ratios of the algorithms. in table we first study the effect of deposition process and reduction process in our dr algorithm. to this end, we define csd and csr to be the common supersequences obtained after the deposition and reduction process, respectively. from table we observed that both the deposition and the reduction processes are effective. the deposition process always output templates with |templated| /|opt| less than for both long and short sequences. in the following tables, we will see that this is much better than results of alphabet, indicating the superiority of -la-sh template. the reduction process can further reduce the lengths of the results by between to characters for n = and by about characters for n = and the performance ratios are correspondingly reduced. the standard deviations for the results of both deposition and reduction processes are not big, indication that both the deposition process and the reduction process give stable results. in table we then compared the various heuristic algorithms – alphabet, tournament, greedy, majority merge with our dr algorithm on these simulated dna datasets. to assist the comparison, we have also included the lower bound, and the average estimated performance ratios. the results in table show very clearly that for the datasets with large k and n, the dr algorithm consistently gives the best results, followed quite closely by mm, while algorithms tour and grdy are quite a bit worse. generally, we observe that the length of the scs obtained increases with the number of sequences, which is to be expected. the performances of the algorithms on medium length sequences also differ slightly from those for long sequences. for n = our dr algorithm produces results that are, on average, shorter than those of mm by characters, by characters than those of grdy, and by characters than those of tour. for long sequences, the difference are more pronounced, by characters for mm, by characters for grdy, and by characters for tour. similar to the results observed in, the performance ratios obtained by all the algorithms are quite a bit below the worst-case ratio of for the trivial alphabet algorithm. the standard deviation results in table also show that dr algorithm is relatively stable – more stable than grdy and tour, but not as stable the mm algorithm. we have not done a similar comparison on simulated protein sequences, but we expect that the relative performances of these algorithms on random protein sequences would be similar to those for random dna sequences. in the next section, we show results on real dna and protein sequences. results on real biological sequences in this section, we compared the algorithms alphabet and mm with our dr on datasets obtained from real dna and protein sequences. for this study, we have to exclude the grdy and tour algorithms since their performances are much worse than mm or dr, and they are also very time-consuming on these datasets. for this experimental comparison, we have randomly selected dna sequences from the ncbi viral genomes. these dna sequences are truncated so that they have lengths of and and combined to obtained many datasets that are grouped into four cases with k = and and randomly selected datasets for each setting, as shown in table the protein sequences are from swissprot and these have been truncated to length and we have used k = and to truncate datasets, and randomly selected datasets for each setting. these datasets are grouped into three cases as shown in table both real dna and protein sequences datasets are available as additional supplemental materials. the comparison results for mm and dr algorithms on these selected dna and protein sequences are shown in table the results for real dna sequences are similar to those for simulated dna sequences. again, the results clearly show that dr consistently outperform the mm algorithm for both type of sequences. the performance ratio |csdr|/|opt| of dr algorithm is about for dna sequences with length and and ~ for protein sequences with length these are much less than the approximation ratios. we also observe that the length of the scs obtained increases with the number of sequences. comparing table with table we also observed that the performance ratios for mm and dr are generally a little bigger for real dna sequences as compared to simulated dna sequences for similar values of k and n. this may be attributed to the fact that the real dna sequences are selected from different viral genomes and thus, there is high variance in the gc contents and this may have resulted in longer scs. whereas, in the simulated dna sequences, the gc content is predefined for each of the simulated dna sequences datasets and this may have resulted in the shorter scs obtained by the algorithms. this observation is also consistent with results in. the results for protein sequences show a similar trend as those for dna sequences. note that the approximation ratio for the alphabet algorithm is for protein sequences. our results show that for dr on protein sequences with n = the performance ratio is smaller than those for mm. the difference in the performance ratios of dr and mm is larger for protein sequences that have a larger alphabet. in terms of the length of the scs result, dr obtains scs results that are between to characters shorter compared to those obtained by mm. the standard deviations observed in table for dna and protein sequences are relatively small, again indicating that both mm and dr algorithms give relatively stable performance. comparison with reduce-expand algorithm the reduce-expand algorithm is currently one of the best algorithms for the general scs problem for small scs instances. because of the high running time of the re algorithm, we have only compared re with our dr algorithm on simulated datasets with relatively few, short dna sequences, as well as small datasets of real dna and protein sequences. the results on simulated datasets are shown in table the results in table indicate that dr is only comparable to re in the lengths of the results when there are only sequences, but outperform re in the lengths of the results when the number of sequences is over the more sequences, and the longer the sequences, the larger differences between the length of the results of dr and re. especially for longer sequences, the results of dr can be about to characters shorter than the results of re. we have also compared the algorithms alphabet and re with our dr on datasets obtained from real dna and protein sequences. the sequences in datasets are shorter from those in table and the results are shown in table the results on real dna and protein sequences are consistent with the results on simulated sequences. the dr algorithm can outperform the re algorithm by about characters for dna sequences of length the scs results of the dr algorithm are also shorter than the results of the re algorithm by more than characters on protein sequences. the more sequences, and the longer the sequences, the larger differences between the length of the results of the dr and re algorithm. computational efficiency our deposition and reduction algorithm has time complexity of o and space complexity of o. in our experiments, the dr algorithm is very fast, even for large scs datasets – for example, for sequences of length each, it take an average of 5– minutes per instance. in comparison to existing algorithms, it is slower than majority merge, min height, but it is much faster than greedy and tournament algorithms. the dr algorithm is also much faster than the reduce-expand algorithm. for a simulated dna dataset with sequences each of length the dr algorithm can get result in less than seconds, while the reduce-expand algorithm needs more than minutes. the actual computer memory used by the dr algorithm is about m for some of our very large datasets; majority merge needs about m for these same datasets. the software is available upon request, and the web services portal will be available soon.  in this paper, we have proposed a deposition and reduction algorithm for solving large scs instances. the dr algorithm is composed of the deposition process to generate good templates, and the reduction process to reduce templates from template pool to get short result. these processes are shown to be powerful for the scs problem. we have compared the performance of our dr algorithm with some of the best heuristic algorithms on different sequences datasets, especially on many long sequences. the dr algorithm has superior performance than alphabet, tournament, greedy and majority merge algorithms in practice, especially on many long sequences. it also outperforms the reduce-expand algorithm for sequences of length 50~ the dr algorithm is also very efficient in time and space, which partially answer the question that barone et al. raised about how to design efficient heuristic algorithm on many long sequences. the deposition and reduction algorithm is an extension of our previous study for scs problem on dna oligos. to our best knowledge, our deposition and reduction is one of the best heuristic algorithms for the scs problem on biological sequences such as the dna and protein sequences, especially for datasets with many long sequences. we believe that the use of the deposition and reduction algorithm can facilitate the biological sequencing process for bioinformatics researches. there are many other post process strategies for the scs problem, such as better look ahead strategies, which may lead to better performance. we are currently trying to further analyze these strategies for scs problems by comparing the results of different strategies. as a general computational framework, this deposition and reduction algorithm can also be applied on more general applications such as text comparison and compression, query optimization and scheduling. we will also work on these more general problems in the future. supplementary material additional file 1 real dna sequences dna sequences are obtained from ncbi viral genomes, accessed on 01/01/. sequences are randomly selected from different genome sequences. the specific length and number of sequences are specified for each dataset. there are randomly selected datasets. file name indicate the number of sequences, sequence length, and dataset number. for example, file name "dna_n100_k500_5" indicate that it is dna sequences dataset, with sequences, each truncated to length of and this is number datasets for this setting. each sequence is represented as a row in the dataset file. click here for file additional file 2 real protein sequences protein sequences are obtained from swiss-prot release of 04-jan-. sequences are randomly selected from different protein sequences. the specific length and number of sequences are specified for each protein dataset. there are randomly selected datasets. file name indicate the number of sequences, sequence length, and dataset number. for example, file name "protein_n100_k500_5" indicate that it is protein sequences dataset, with sequences, each truncated to length of and this is number datasets for this setting. each sequence is represented as a row in the data file. click here for file acknowledgements we thank anonymous reviewers for valuable comments on the paper. this work was partially supported by the national university of singapore under grant r252-000-199- this article has been published as part of bmc bioinformatics volume supplement 2006: symposium of computations in bioinformatics and bioscience. the full contents of the supplement are available online at. figures and tables sequences length of cs k n lb r' d r' r each row of the table represents randomly generated instances. for each row, we list the average value for lb, |csd|, and |csr|, their standard deviations, and the estimated performance ratios r'd and r'r sequences length of cs k n lb alpha ratio tour ratio grdy ratio mm ratio dr ratio the average and standard deviation over randomly generated instances are given. the estimated performance ratios are also given for each algorithm. sequences length of cs k n lb alpha ratio mm ratio dr ratio dna sequences protein sequences the average and standard deviation are given. the estimated performance ratios are also given for each algorithm. sequences length of scs k n alpha re dr in each cell, the average and standard deviation over randomly generated instances are given. k n alpha re dr dna protein in each cell, the average and standard deviation over randomly generated instances are given.
our evaluation on simulated data and real dna and protein sequences show that our algorithm consistently produces the best results compared to many well-known heuristic algorithms, and especially on large instances. the scs problem is well-known to be np-complete. our dr algorithm provides a partial answer to the open problem of designing efficient heuristic algorithm for scs problem on many long sequences. the algorithm is efficient, both in running time and space complexity and our evaluation shows that it is practical even for scs problems on many long sequences. many heuristic algorithms have been proposed. unfortunately, most do not work well on large scs instances where there are many, long sequences. in this paper, we present a deposition and reduction algorithm for solving large scs instances of biological sequences. it is a key problem in biological sequences analysis. our algorithm has a bounded approximation ratio. the deposition process is responsible for generating a small set of common supersequences; and the reduction process shortens these common supersequences by removing some characters while preserving the common supersequence property. the problem of finding a shortest common supersequence of a set of sequences is an important problem with applications in many areas. there are two processes in our dr algorithm: deposition process, and reduction process. some heuristics work well on a few long sequences; others work well on many short sequences.
 the problem of finding a shortest common supersequence of a set of sequences is an important problem with applications in many areas. it is a key problem in biological sequences analysis. the scs problem is well-known to be np-complete. many heuristic algorithms have been proposed. some heuristics work well on a few long sequences; others work well on many short sequences. unfortunately, most do not work well on large scs instances where there are many, long sequences.  in this paper, we present a deposition and reduction algorithm for solving large scs instances of biological sequences. there are two processes in our dr algorithm: deposition process, and reduction process. the deposition process is responsible for generating a small set of common supersequences; and the reduction process shortens these common supersequences by removing some characters while preserving the common supersequence property. our evaluation on simulated data and real dna and protein sequences show that our algorithm consistently produces the best results compared to many well-known heuristic algorithms, and especially on large instances.  our dr algorithm provides a partial answer to the open problem of designing efficient heuristic algorithm for scs problem on many long sequences. our algorithm has a bounded approximation ratio. the algorithm is efficient, both in running time and space complexity and our evaluation shows that it is practical even for scs problems on many long sequences. june 20– symposium of computations in bioinformatics and bioscience in conjunction with the international multi-symposiums on computer and computational sciences hangzhou, china 