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

A finite state machine algorithm for finding restriction sites and other pattern matching applications.

R Smith1

  • 1Public Health Research Institute, New York, NY 10016.

Computer Applications in the Biosciences : CABIOS
|November 1, 1988
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

Paget's disease of bone.

BMJ (Clinical research ed.)·1992
Same author

Nonuniform expression of a mouse mammary tumor virus-driven int-2/Fgf-3 transgene in pregnancy-responsive breast tumors.

Cell growth & differentiation : the molecular biology journal of the American Association for Cancer Research·1992
Same author

Proviral insertions near cyclin D1 in mouse lymphomas: a parallel for BCL1 translocations in human B-cell neoplasms.

Oncogene·1992
Same author

Beta-endrophin immunoreactivity during human pregnancy.

The Journal of clinical endocrinology and metabolism·1992
Same author

Whistle blowing: a curse on ineffective organisations.

BMJ (Clinical research ed.)·1992
Same author

Using a mock trial to make a difficult clinical decision.

BMJ (Clinical research ed.)·1992

This study introduces a new deterministic finite state machine algorithm for finding restriction enzyme recognition sites, significantly improving speed from O(NM) to O(N). This faster method enhances DNA sequence analysis and has potential applications in specialized hardware for database machines.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Design

Background:

  • Current algorithms for identifying restriction endonuclease recognition sites rely on brute-force methods.
  • These existing algorithms have a time complexity of O(NM), where N is the sequence length and M is the total length of sites.

Purpose of the Study:

  • To present a novel deterministic finite state machine (FSM) algorithm for efficient recognition site identification.
  • To improve the time complexity of finding restriction enzyme recognition sites.

Main Methods:

  • Developed a deterministic finite state machine algorithm for pattern matching.
  • The algorithm processes sequences in a single pass with minimal memory requirements.

Main Results:

Related Experiment Videos

  • The new FSM algorithm achieves a linear time complexity of O(N).
  • Memory usage can be optimized to O(M) with a slight modification, though potentially increasing complexity.

Conclusions:

  • The proposed FSM algorithm offers a significant speed improvement for restriction site identification.
  • The algorithm's efficiency and adaptability make it suitable for hardware implementation in specialized database machines.