Skip Navigation

This Article
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (155)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Rigoutsos, I.
Right arrow Articles by Floratos, A.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Rigoutsos, I.
Right arrow Articles by Floratos, A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Bioinformatics, Vol 14, 55-67, Copyright © 1998 by Oxford University Press

ARTICLES

Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm [published erratum appears in Bioinformatics 1998;14(2):229]

I Rigoutsos and A Floratos
Computational Biology Center, IBM Thomas J. Watson Research Center, York Town Heights, NY 10598, USA.

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.
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Proc. Natl. Acad. Sci. USAHome page
Y. Hirakawa, K. Nagamune, and K.-i. Ishida
Protein targeting into secondary plastids of chlorarachniophytes
PNAS, August 4, 2009; 106(31): 12820 - 12825.
[Abstract] [Full Text] [PDF]

Home page
 J. Bacteriol.Home page
F. G. Healy, K. P. Eaton, P. Limsirichai, J. F. Aldrich, A. K. Plowman, and R. R. King
Characterization of {gamma}-Butyrolactone Autoregulatory Signaling Gene Homologs in the Angucyclinone Polyketide WS5995B Producer Streptomyces acidiscabies
J. Bacteriol., August 1, 2009; 191(15): 4786 - 4797.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. T.-H. Chang, T.-Y. Chien, and C.-Y. Chen
seeMotif: exploring and visualizing sequence motifs in 3D structures
Nucleic Acids Res., July 1, 2009; 37(suppl_2): W552 - W558.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
S. Zhang, W. Su, and J. Yang
ARCS-Motif: discovering correlated motifs from unaligned biological sequences
Bioinformatics, January 15, 2009; 25(2): 183 - 189.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
A. Ritz, G. Shakhnarovich, A. R. Salomon, and B. J. Raphael
Discovery of phosphorylation motif mixtures in phosphoproteomics data
Bioinformatics, January 1, 2009; 25(1): 14 - 21.
[Abstract] [Full Text] [PDF]

Home page
 DNA ResHome page
Y. Shimoda, H. Mitsui, H. Kamimatsuse, K. Minamisawa, E. Nishiyama, Y. Ohtsubo, Y. Nagata, M. Tsuda, S. Shinpo, A. Watanabe, et al.
Construction of Signature-tagged Mutant Library in Mesorhizobium loti as a Powerful Tool for Functional Genomics
DNA Res, October 1, 2008; 15(5): 297 - 308.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
T.-Y. Chien, D. T.-H. Chang, C.-Y. Chen, Y.-Z. Weng, and C.-M. Hsu
E1DS: catalytic site prediction based on 1D signatures of concurrent conservation
Nucleic Acids Res., July 1, 2008; 36(suppl_2): W291 - W296.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
A. Tsirigos and I. Rigoutsos
Human and mouse introns are linked to the same processes and functions through each genome's most frequent non-conserved motifs
Nucleic Acids Res., June 1, 2008; 36(10): 3484 - 3493.
[Abstract] [Full Text] [PDF]

Home page
 Cancer Res.Home page
M. O. Hoque, M. S. Kim, K. L. Ostrow, J. Liu, G. B. A. Wisman, H. L. Park, M. L. Poeta, C. Jeronimo, R. Henrique, A. Lendvai, et al.
Genome-Wide Promoter Analysis Uncovers Portions of the Cancer Methylome
Cancer Res., April 15, 2008; 68(8): 2661 - 2670.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
D. He and J. Parkinson
SubSeqer: a graph-based approach for the detection and identification of repetitive elements in low-complexity sequences
Bioinformatics, April 1, 2008; 24(7): 1016 - 1017.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
C.-M. Hsu, C.-Y. Chen, and B.-J. Liu
Corrigendum
Nucleic Acids Res., March 27, 2008; 36(4): 1400 - 1406.
[Abstract] [Full Text] [PDF]

Home page
 Mol. Cell. ProteomicsHome page
M. L. Miller, S. Hanke, A. M. Hinsby, C. Friis, S. Brunak, M. Mann, and N. Blom
Motif Decomposition of the Phosphotyrosine Proteome Reveals a New N-terminal Binding Motif for SHIP2
Mol. Cell. Proteomics, January 1, 2008; 7(1): 181 - 192.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
Y. Cai, B. Hartnett, C. Gustafsson, and J. Peccoud
A syntactic model to design and verify synthetic genetic constructs derived from standard biological parts
Bioinformatics, October 15, 2007; 23(20): 2760 - 2767.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
N. E. Davey, R. J. Edwards, and D. C. Shields
The SLiMDisc server: short, linear motif discovery in proteins
Nucleic Acids Res., July 13, 2007; 35(suppl_2): W455 - W459.
[Abstract] [Full Text] [PDF]

Home page
 Plant Physiol.Home page
I. J.E. Stulemeijer, J. W. Stratmann, and M. H.A.J. Joosten
Tomato Mitogen-Activated Protein Kinases LeMPK1, LeMPK2, and LeMPK3 Are Activated during the Cf-4/Avr4-Induced Hypersensitive Response and Have Distinct Phosphorylation Specificities
Plant Physiology, July 1, 2007; 144(3): 1481 - 1494.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
E. Wijaya, K. Rajaraman, S.-M. Yiu, and W.-K. Sung
Detection of generic spaced motifs using submotif pattern mining
Bioinformatics, June 15, 2007; 23(12): 1476 - 1485.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
J. S. Papadopoulos and R. Agarwala
COBALT: constraint-based alignment tool for multiple protein sequences
Bioinformatics, May 1, 2007; 23(9): 1073 - 1079.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
M. Hohl and M. A. Ragan
Is Multiple-Sequence Alignment Required for Accurate Inference of Phylogeny?
Syst Biol, April 1, 2007; 56(2): 206 - 221.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
K. Ye, W. A. Kosters, and A. P. IJzerman
An efficient, versatile and scalable pattern growth approach to mine frequent patterns in unaligned protein sequences
Bioinformatics, March 15, 2007; 23(6): 687 - 693.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
G. Thibault, J. Yudin, P. Wong, V. Tsitrin, R. Sprangers, R. Zhao, and W. A. Houry
Specificity in substrate and cofactor recognition by the N-terminal domain of the chaperone ClpX
PNAS, November 21, 2006; 103(47): 17724 - 17729.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
N. E. Davey, D. C. Shields, and R. J. Edwards
SLiMDisc: short, linear motif discovery, correcting for common evolutionary descent
Nucleic Acids Res., July 19, 2006; 34(12): 3546 - 3554.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. GuhaThakurta
Computational identification of transcriptional regulatory elements in DNA sequence
Nucleic Acids Res., July 19, 2006; 34(12): 3585 - 3598.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
V. Neduva and R. B. Russell
DILIMOT: discovery of linear motifs in proteins.
Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W350 - W355.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
C.-M. Hsu, C.-Y. Chen, and B.-J. Liu
MAGIIC-PRO: detecting functional signatures by efficient discovery of long patterns in protein sequences.
Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W356 - W361.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
I. Rigoutsos, T. Huynh, K. Miranda, A. Tsirigos, A. McHardy, and D. Platt
Short blocks from the noncoding parts of the human genome have instances within nearly all known genes and relate to biological processes
PNAS, April 25, 2006; 103(17): 6605 - 6610.
[Abstract] [Full Text] [PDF]

Home page
 Physiol. GenomicsHome page
A. Sivakumar, C. Wilton, and L. Holm
From sequences to a functional unit
Physiol Genomics, March 13, 2006; 25(1): 1 - 8.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
Q.-w. Dong, X.-l. Wang, and L. Lin
Application of latent semantic analysis to protein remote homology detection
Bioinformatics, February 1, 2006; 22(3): 285 - 290.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
K. L. Jensen, M. P. Styczynski, I. Rigoutsos, and G. N. Stephanopoulos
A generic motif discovery algorithm for sequential data
Bioinformatics, January 1, 2006; 22(1): 21 - 28.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
L. Goldovsky, P. Janssen, D. Ahren, B. Audit, I. Cases, N. Darzentas, A. J. Enright, N. Lopez-Bigas, J. M. Peregrin-Alvarez, M. Smith, et al.
CoGenT++: an extensive and extensible data environment for computational genomics
Bioinformatics, October 1, 2005; 21(19): 3806 - 3810.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
R. G. Beiko, C. X. Chan, and M. A. Ragan
A word-oriented approach to alignment validation
Bioinformatics, May 15, 2005; 21(10): 2230 - 2239.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
S. Mahony, D. Hendrix, A. Golden, T. J. Smith, and D. S. Rokhsar
Transcription factor binding site identification using the self-organizing map
Bioinformatics, May 1, 2005; 21(9): 1807 - 1814.
[Abstract] [Full Text] [PDF]

Home page
 JCBHome page
E. Kiesler, M. E. Hase, D. Brodin, and N. Visa
Hrp59, an hnRNP M protein in Chironomus and Drosophila, binds to exonic splicing enhancers and is required for expression of a subset of mRNAs
J. Cell Biol., March 28, 2005; 168(7): 1013 - 1025.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
T. Huynh and I. Rigoutsos
The web server of IBM's Bioinformatics and Pattern Discovery group: 2004 update
Nucleic Acids Res., July 1, 2004; 32(suppl_2): W10 - W15.
[Abstract] [Full Text] [PDF]

Home page
 Physiol. GenomicsHome page
M. S. Wong, R. M. Raab, I. Rigoutsos, G. N. Stephanopoulos, and J. K. Kelleher
Metabolic and transcriptional patterns accompanying glutamine depletion and repletion in mouse hepatoma cells: a model for physiological regulatory networks
Physiol Genomics, January 15, 2004; 16(2): 247 - 255.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
I. Rigoutsos, P. Riek, R. M. Graham, and J. Novotny
Structural details (kinks and non-{alpha} conformations) in transmembrane helices are intrahelically determined and can be predicted by sequence pattern descriptors
Nucleic Acids Res., August 1, 2003; 31(15): 4625 - 4631.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
T. Huynh, I. Rigoutsos, L. Parida, D. Platt, and T. Shibuya
The web server of IBM's Bioinformatics and Pattern Discovery group
Nucleic Acids Res., July 1, 2003; 31(13): 3645 - 3650.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
J. Klass, F. V. Murphy IV, S. Fouts, M. Serenil, A. Changela, J. Siple, and M. E. A. Churchill
The role of intercalating residues in chromosomal high-mobility-group protein DNA binding, bending and specificity
Nucleic Acids Res., June 1, 2003; 31(11): 2852 - 2864.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
L. M. Ettwiller, J. Rung, and E. Birney
Discovering Novel cis-Regulatory Motifs Using Functional Networks
Genome Res., May 1, 2003; 13(5): 883 - 895.
[Abstract] [Full Text] [PDF]

Home page
 J. Virol.Home page
I. Rigoutsos, J. Novotny, T. Huynh, S. T. Chin-Bow, L. Parida, D. Platt, D. Coleman, and T. Shenk
In Silico Pattern-Based Analysis of the Human Cytomegalovirus Genome
J. Virol., April 1, 2003; 77(7): 4326 - 4344.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
I. Rigoutsos, T. Huynh, A. Floratos, L. Parida, and D. Platt
Dictionary-driven protein annotation
Nucleic Acids Res., September 1, 2002; 30(17): 3901 - 3916.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
T. Shibuya and I. Rigoutsos
Dictionary-driven prokaryotic gene finding
Nucleic Acids Res., June 15, 2002; 30(12): 2710 - 2725.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
H. J. Bussemaker, H. Li, and E. D. Siggia
Building a dictionary for genomes: Identification of presumptive regulatory sites by statistical analysis
PNAS, August 10, 2000; (2000) 180265397.
[Abstract] [Full Text]

Home page
 Proc. Natl. Acad. Sci. USAHome page
H. J. Bussemaker, H. Li, and E. D. Siggia
From the Cover: Building a dictionary for genomes: Identification of presumptive regulatory sites by statistical analysis
PNAS, August 29, 2000; 97(18): 10096 - 10100.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.