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

An approximate matching algorithm for finding (sub-)optimal sequences in S-attributed grammars.

J Waldispühl1, B Behzadi, J-M Steyaert

  • 1Ecole Polytechnique, Palaiseau, France. waldispu@lix.polytechnique.fr

Bioinformatics (Oxford, England)
|October 19, 2002
PubMed
Summary
This summary is machine-generated.

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

Computing the partition function and sampling for saturated secondary structures of RNA, with respect to the Turner energy model.

Journal of computational biology : a journal of computational molecular cell biology·2007
Same author

Predicting transmembrane beta-barrels and interstrand residue interactions from sequence.

Proteins·2006
Same author

transFold: a web server for predicting the structure and residue contacts of transmembrane beta-barrels.

Nucleic acids research·2006
Same author

Energy landscape of k-point mutants of an RNA molecule.

Bioinformatics (Oxford, England)·2005
Same author

[Clinical-psychological examinations on the diagnosis and therapy of psychic maldevelopment].

Zeitschrift fur Psychologie mit Zeitschrift fur angewandte Psychologie·1980
Same journal

Biomedical Concept Recognition with Error-aware Negative-enhanced Ranking Framework.

Bioinformatics (Oxford, England)·2026
Same journal

TEDLH: Domain HMMs for sensitive detection of remote homologues.

Bioinformatics (Oxford, England)·2026
Same journal

PLNFGL: Joint Estimation of Multi-Condition Gene Networks from Single-cell RNA-seq Data.

Bioinformatics (Oxford, England)·2026
Same journal

MCFST: Spatial domain identification method based on multi-view graph convolutional network and graph fusion network.

Bioinformatics (Oxford, England)·2026
Same journal

SpaBiT: Enhancing Spatial Transcriptomics Resolution via Bidirectional Attention Transformers.

Bioinformatics (Oxford, England)·2026
Same journal

EDEL: Enhancing Dense Retrievers for Curation of Biomedical Knowledge Bases.

Bioinformatics (Oxford, England)·2026
See all related articles

This study introduces a new algorithm for S-attributed grammars, enabling analysis of approximate sequences and near-optimal attributes crucial for biological sequence analysis. The method efficiently finds optimal attributes for sequences within a defined distance, enhancing sequence analysis capabilities.

Area of Science:

  • Computational Biology
  • Formal Language Theory

Background:

  • S-attributed grammars generalize Context-Free grammars for sequence analysis.
  • They allow for long-range constraints, applicable to problems like RNA folding.
  • Current algorithms focus on optimal attributes, but near-optimal and approximate sequences are often more biologically relevant.

Purpose of the Study:

  • To develop flexible and powerful algorithms for generalized sequence analyses.
  • To compute optimal attributes for approximate sequences within a specified error threshold.
  • To address the need for analyzing sequences beyond perfect matches in biological contexts.

Main Methods:

  • Presentation of a foundational algorithm for S-attributed grammars.
  • The algorithm computes optimal attributes for approximate strings within a given distance M.

Related Experiment Videos

  • Analysis of computational complexity: O(n(r+1)) time and O(n^2) space.

    • Main Results:

    • An efficient algorithm is presented for finding optimal attributes of approximate sequences.
    • The algorithm's time complexity is O(n(r+1)) and space complexity is O(n^2).
    • Extensions and improvements to the basic algorithm are discussed.

    Conclusions:

    • The developed algorithm provides a significant advancement for sequence analysis using S-attributed grammars.
    • It enables the meaningful analysis of near-optimal attributes and approximate sequences in biological applications.
    • The work lays the groundwork for more flexible and powerful computational tools in bioinformatics.