| Title | A linear time algorithm for finding all maximal scoring subsequences. |
| Publication Type | Journal Article |
| Year of Publication | 1999 |
| Authors | Ruzzo WL, Tompa M |
| Journal | Proceedings / ... International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology |
| Pagination | 234-41 |
| Date or Month Published | 1999 |
| ISSN | 1553-0833 |
| Keywords | Algorithms, Models, Statistical, Sequence Analysis, DNA, Software, Time Factors |
| Abstract | Given a sequence of real numbers ("scores"), we present a practical linear time algorithm to find those nonoverlapping, contiguous subsequences having greatest total scores. This improves on the best previously known algorithm, which requires quadratic time in the worst case. The problem arises in biological sequence analysis, where the high-scoring subsequences correspond to regions of unusual composition in a nucleic acid or protein sequence. For instance, Altschul, Karlin, and others have used this approach to identify transmembrane regions, DNA binding domains, and regions of high charge in proteins. |
| Downloads | http://www.ncbi.nlm.nih.gov/pubmed/10786306?dopt=Abstract |
| Alternate Journal | Proc Int Conf Intell Syst Mol Biol |
| Citation Key | 1895 |
| PubMed ID | 10786306 |
