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 efficient string matching algorithm with K substitutions for nucleotide and amino acid sequences.

G M Landau1, U Vishkin, R Nussinov

  • 1Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Israel.

Journal of Theoretical Biology
|June 21, 1987
PubMed
Summary

We developed a new algorithm to find approximate pattern matches in large texts, allowing for up to k substitutions. This method accelerates sequence comparison in bioinformatics.

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

Mutations in LZTR1 drive human disease by dysregulating RAS ubiquitination.

Science (New York, N.Y.)·2018
Same author

Contribution of salt bridges toward protein thermostability.

Journal of biomolecular structure & dynamics·2012
Same author

GOSSIP: a method for fast and accurate global alignment of protein structures.

Bioinformatics (Oxford, England)·2011
Same author

Towards drugs targeting multiple proteins in a systems biology approach.

Current topics in medicinal chemistry·2007
Same author

MASS: multiple structural alignment by secondary structures.

Bioinformatics (Oxford, England)·2003
Same author

Transient, highly populated, building blocks folding model.

Cell biochemistry and biophysics·2002

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Design

Background:

  • Sequence comparison is fundamental to bioinformatics.
  • Existing algorithms struggle with approximate matching efficiently.
  • Identifying homologous sequences requires handling mutations and errors.

Purpose of the Study:

  • To present a novel algorithm for approximate pattern matching.
  • To enable efficient identification of sequences with up to k substitutions.
  • To provide a tool applicable to nucleotide and amino acid sequence analysis.

Main Methods:

  • Developed an algorithm for approximate string matching.
  • Analyzed algorithm runtime complexity as O(k(m log m + n)).
  • Assessed space complexity as O(nk).

Related Experiment Videos

Main Results:

  • The algorithm efficiently finds all pattern occurrences with at most k substitutions.
  • Achieved a time complexity of O(k(m log m + n)).
  • Requires O(nk) space complexity.

Conclusions:

  • The new algorithm offers a significant advancement for sequence comparison tasks.
  • Its efficiency makes it suitable for large-scale genomic and proteomic data analysis.
  • Directly applicable to challenges in molecular biology and evolutionary studies.