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

Locating alignments with k differences 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.

Computer Applications in the Biosciences : CABIOS
|March 1, 1988
PubMed
Summary

This study introduces two algorithms for pattern matching in texts with up to k differences. The first finds pattern occurrences in O(nk) time, while the second finds subsequence alignments in O(nmk) time.

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:

  • Computer Science
  • Bioinformatics
  • Computational Biology

Background:

  • Approximate string matching is crucial for analyzing biological sequences and text data.
  • Identifying patterns with variations is essential in fields like genomics and natural language processing.

Purpose of the Study:

  • To develop efficient algorithms for approximate pattern matching in sequences.
  • To address the need for algorithms that can find patterns with a specified number of differences (k).

Main Methods:

  • Algorithm 1: Identifies occurrences of a pattern (length m) within a text (length n) allowing up to k differences, with a time complexity of O(nk).
  • Algorithm 2: Finds all subsequence alignments between a pattern and a text with at most k differences, featuring a time complexity of O(nmk).

Related Experiment Videos

Main Results:

  • The first algorithm provides a time-efficient solution for finding approximate pattern occurrences.
  • The second algorithm offers a simple and programmable method for subsequence alignment with k differences.

Conclusions:

  • The developed algorithms offer practical solutions for approximate string matching problems.
  • These algorithms can be valuable tools in sequence analysis and related computational fields.