Loading...
Please wait, while we are loading the content...
Similar Documents
A learning algorithm for the longest common subsequence problem
| Content Provider | ACM Digital Library |
|---|---|
| Author | Breimer, Eric A. Goldberg, Mark K. Lim, Darren T. |
| Copyright Year | 2003 |
| Abstract | We present an experimental study of a learning algorithm for the longest common subsequence problem, $\textit{LCS}.$ Given an arbitrary input domain, the algorithm learns an $\textit{LCS}-procedure$ tailored to that domain. The learning is done with the help of an oracle, which can be any $\textit{LCS}-algorithm.$ After solving a limited number of training inputs using an oracle, the learning algorithm outputs a new $\textit{LCS}-procedure.Our$ experiments demonstrate that, by allowing a slight loss of optimality, learning yields a procedure which is significantly faster than the oracle. The oracle used for the experiments is the $\textit{np}-procedure$ by Wu et al., a modification of Myers' classical $\textit{LCS}-algorithm.$ We show how to scale up the results of learning on small inputs to inputs of arbitrary lengths. For the domain of two random 2-symbol inputs of length $\textit{n},$ learning yields a program with 0.999 expected accuracy, which runs in $O(n^{1.41})-time,$ in contrast with $O(n^{2}/log$ $\textit{n})$ running time of the fastest theoretical algorithm that produces optimal solutions. For the domain of random 2-symbol inputs of length 100,000, the program runs 10.5 times faster than the $\textit{np}-procedure,$ producing 0.999- accurate outputs. The scaled version of the evolved algorithm applied to random inputs of length 1 million runs approximately 30 times faster than the $\textit{np}-procedure$ while constructing 0.999- accurate solutions. We apply the evolved algorithm to DNA sequences of various lengths by training on random 4-symbol sequences of up to length 10,000. The evolved algorithm, scaled up to the lengths of up to 1.8 million, produces solutions with the 0.998-accuracy in a fraction of the time used by the $\textit{np}.$ |
| File Format | |
| ISSN | 10846654 |
| e-ISSN | 10846654 |
| DOI | 10.1145/996546.996552 |
| Journal | Journal of Experimental Algorithmics (JEA) |
| Volume Number | 8 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2003-12-01 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Content Type | Text |
| Resource Type | Article |
| Subject | Theoretical Computer Science |
