The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm.
Abstract
MOTIVATION: The discovery of motifs in biological sequences is an important problem. RESULTS: This paper presents a new algorithm for the discovery of rigid patterns (motifs) in biological sequences. Our method is combinatorial in nature and able to produce all patterns that appear in at least a (user-defined) minimum number of sequences, yet it manages to be very efficient by avoiding the enumeration of the entire pattern space. Furthermore, the reported patterns are maximal: any reported pattern cannot be made more specific and still keep on appearing at the exact same positions within the input sequences. The effectiveness of the proposed approach is showcased on a number of test cases which aim to: (i) validate the approach through the discovery of previously reported patterns; (ii) demonstrate the capability to identify automatically highly selective patterns particular to the sequences under consideration. Finally, experimental analysis indicates that the algorithm is output sensitive, i.e. its running time is quasi-linear to the size of the generated output.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,940
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
The SWISS-PROT protein sequence data bank and its supplement TrEMBL
Bairoch, A., & Apweiler, R. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.1.31 · Cited by 3,587
Watson, J. D. (1970) · Cold Spring Harbor Laboratory Institutional Repository (Cold Spring Harbor Laboratory) · Cited by 2,062
On the Complexity of Multiple Sequence Alignment
WANG, L., & JIANG, T. (1994) · Journal of Computational Biology · doi:10.1089/cmb.1994.1.337 · Cited by 934
The Complexity of Some Problems on Subsequences and Supersequences
Maier, D. (1978) · Journal of the ACM · doi:10.1145/322063.322075 · Cited by 616
The Multiple Sequence Alignment Problem in Biology
Carrillo-Calvet, H., & Lipman, D. J. (1988) · SIAM Journal on Applied Mathematics · doi:10.1137/0148063 · Cited by 526
The protein identification resource (PIR)
Sidman, K. E., George, D. G., Barker, W. C., & Hunt, L. T. (1988) · Nucleic Acids Research · doi:10.1093/nar/16.5.1869 · Cited by 386
Protein Family Classification Based on Searching a Database of Blocks
Henikoff, S., & Henikoff, J. G. (1994) · Genomics · doi:10.1006/geno.1994.1018 · Cited by 363
Arents, G., & Moudrianakis, E. N. (1993) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.90.22.10489 · Cited by 341
Approaches to the Automatic Discovery of Patterns in Biosequences
BRAZMA, A., JONASSEN, I., EIDHAMMER, I., & GILBERT, D. (1998) · Journal of Computational Biology · doi:10.1089/cmb.1998.5.279 · Cited by 303
Finding flexible patterns in unaligned protein sequences
Jonassen, I., Collins, J. F., & Higgins, D. G. (1995) · Protein Science · doi:10.1002/pro.5560040817 · Cited by 297
Automatic generation of primary sequence patterns from sets of related protein sequences.
Smith, R. F., & Smith, T. F. (1990) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.87.1.118 · Cited by 286
Finding sequence motifs in groups of functionally related proteins.
Smith, H. O., Annau, T. M., & Chandrasegaran, S. (1990) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.87.2.826 · Cited by 203
A variety of DNA-binding and multimeric proteins contain the histone fold motif
Baxevanis, A. D., Arents, G., Moudrianakis, E. N., & Landsman, D. (1995) · Nucleic Acids Research · doi:10.1093/nar/23.14.2685 · Cited by 203
The European Bioinformatics Institute (EBI) databases
Emmert, D. B., Stoehr, P. J., Stoesser, G., & Cameron, G. N. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.17.3445 · Cited by 181
Pattern recognition in several sequences: Consensus and alignment
Waterman, M. S., Arratia, R., & Galas, D. J. (1984) · Bulletin of Mathematical Biology · doi:10.1007/bf02459500 · Cited by 158
Comprehensive study on iterative algorithms of multiple sequence alignment
Hirosawa, M., Totoki, Y., Hoshida, M., & Ishikawa, M. (1995) · Computer applications in the biosciences · doi:10.1093/bioinformatics/11.1.13 · Cited by 133
Detecting Patterns in Protein Sequences
Neuwald, A. F., & Green, P. (1994) · Journal of Molecular Biology · doi:10.1006/jmbi.1994.1407 · Cited by 105
[20] Mutation data matrix and its uses
George, D. G., Barker, W. C., & Hunt, L. T. (1990) · Methods in enzymology on CD-ROM/Methods in enzymology · doi:10.1016/0076-6879(90)83022-2 · Cited by 97
Kapp, O. H., Moens, L. J., Vanfleteren, J., Trotman, C. N. A., Suzuki, T., & Vinogradov, S. N. (1995) · Protein Science · doi:10.1002/pro.5560041024 · Cited by 89
A method for fast database search for allk-nucleotide repeats
Benson, G., & Waterman, M. S. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.22.4828 · Cited by 77
A flexible multiple sequence alignment program
Martínez, H. M. (1988) · Nucleic Acids Research · doi:10.1093/nar/16.5.1683 · Cited by 74
Discovering active motifs in sets of related protein sequences and using them for classification
Wang, J. T. L., Marr, T. G., Shasha, D. E., Shapiro, B. A., & Chirn, G. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.14.2769 · Cited by 49
Enumerating and ranking discrete motifs.
Nevill-Manning, C. G., Sethi, K. S., Wu, T. D., & Brutlag, D. L. (1997) · PubMed · Cited by 38
Parallel origins of the nucleosome core and eukaryotic transcription from Archaea
Ouzounis, C., & Kyrpides, N. C. (1996) · Journal of Molecular Evolution · doi:10.1007/bf02198849 · Cited by 33
Histone and histone fold sequences and structures: a database
Baxevanis, A. D., & Landsman, D. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.1.272 · Cited by 13
Cited by
Miranda, K. C., Huynh, T., Tay, Y., Ang, Y.-S., Tam, W.-L., Thomson, A. M., Lim, B., & Rigoutsos, I. (2006) · Cell · doi:10.1016/j.cell.2006.07.031 · Cited by 2,063
Self-citationDNA binding sites: representation and discovery
Stormo, G. D. (2000) · Bioinformatics · doi:10.1093/bioinformatics/16.1.16 · Cited by 1,502
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
COBALT: constraint-based alignment tool for multiple protein sequences
Papadopoulos, J. S., & Agarwala, R. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm076 · Cited by 1,127
Schwartz, D., & Gygi, S. P. (2005) · Nature Biotechnology · doi:10.1038/nbt1146 · Cited by 879
Metadata
- Authors
- Rigoutsos, I., & Floratos, A.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 1998-01-01
- Volume
- 14
- Issue
- 1
- Pages
- 55-67
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2028903194
- Cited by
- 557
- References
- 29
- FWCI
- 13.57
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.