Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Efficient detection of unusual words.

A Apostolico1, M E Bock, S Lonardi

  • 1Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA. axa@cs.purdue.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|July 13, 2000
PubMed
Summary

This study introduces a global suffix tree annotation method for detecting over/underrepresented words in biological sequences. This approach efficiently identifies significant sequence patterns, improving anomaly detection accuracy.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Cisplatin-gemcitabine-durvalumab reintroduction in advanced biliary tract cancer: a multinational real-world analysis.

ESMO open·2026
Same author

Distinct molecular and clinical aggressiveness in very early-onset metastatic colorectal cancer: survival and genomic divergence between patients aged 30-39 versus 40-49 years.

ESMO open·2026
Same author

Checkpoint inhibitors in microsatellite instability-high metastatic colorectal cancer: treatment strategies, specificities, and care management questions.

ESMO gastrointestinal oncology·2026
Same author

A randomised study of encorafenib, cetuximab, and FOLFIRI versus FOLFIRI with or without bevacizumab in BRAF V600E-mutant colorectal cancer: BREAKWATER Cohort 3.

Annals of oncology : official journal of the European Society for Medical Oncology·2026
Same author

Baseline neutrophil-to-eosinophil ratio and neutrophil-to-lymphocyte ratio as prognostic markers in patients with unresectable biliary tract cancer treated with gemcitabine-cisplatin-durvalumab: an international, multicentre, retrospective cohort study.

ESMO gastrointestinal oncology·2026
Same author

Phase II randomised study of magrolimab combined with bevacizumab-FOLFIRI in patients with previously treated advanced inoperable metastatic colorectal cancer.

ESMO gastrointestinal oncology·2026

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Stringology

Background:

  • Over- and underrepresented words in biological sequences are linked to various functions.
  • Traditional anomaly detection methods exhaustively enumerate and individually analyze words.
  • This can be computationally intensive and may miss complex patterns.

Purpose of the Study:

  • To develop a global approach for detecting anomalous words using suffix tree annotations.
  • To create an efficient preliminary filter for identifying suspicious words in sequences.
  • To analyze sequence behavior under a simple probabilistic model.

Main Methods:

  • Annotating suffix trees with statistical values (mean, variance, significance scores).
  • Utilizing a probabilistic model for sequence generation.

Related Experiment Videos

  • Embedding combinatorial string properties into statistical expressions for optimal computation.

    • Main Results:

    • Achieved time-and-space optimal annotation of suffix trees for mean, variance, and significance.
    • Computed expected value and variance for all substrings in O(n^2) worst-case and O(n log n) expected time/space.
    • Identified candidate over/underrepresented words at internal suffix tree nodes, reducing search space to O(n).

    Conclusions:

    • The global suffix tree annotation method provides an efficient and accurate way to detect sequence anomalies.
    • This approach significantly improves upon traditional methods by reducing computational complexity.
    • Developed global detectors for favored/unfavored words in linear time and space.