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

Non-similarity combinatorial problems

A R Rubinov1, V G Timkovsky

  • 1Department of Transportation Control, National Transport Institute, Moscow, Russia.

Bio Systems
|January 1, 1993
PubMed
Summary

This study explores string non-inclusion problems in computational biology. Researchers developed NP-hardness proofs for non-subsequence problems and polynomial-time algorithms for non-substring problems.

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

Reconstruction of a string from substring precedence data.

Journal of computational biology : a journal of computational molecular cell biologyยท1995
See all related articles

Area of Science:

  • Computational molecular biology
  • Stringology
  • Theoretical computer science

Background:

  • Computational biology frequently studies string similarity problems, such as longest common subsequence/substring and shortest common supersequence/superstring.
  • These problems involve finding strings within or across a set of given strings.

Purpose of the Study:

  • Investigate the computational complexity of inverse string problems: finding the shortest string not included in any string of a finite language, and the longest string that includes no string from a finite language.
  • Determine the complexity status of these non-similarity problems, focusing on string non-inclusion relations.

Main Methods:

  • Utilized graph-based approaches to analyze string non-inclusion.
  • Defined "string alpha is not included in string beta" as either "alpha is not a subsequence of beta" or "alpha is not a substring of beta".

Main Results:

  • Presented NP-hardness proofs for the problem of finding the shortest string not a subsequence of any string in a given finite language.
  • Developed polynomial-time algorithms for the problem of finding the longest string that is not a substring of any string in a given finite language.

Conclusions:

  • The study establishes different complexity classes for string non-inclusion problems based on subsequence versus substring interpretations.
  • Highlights the utility of graph approaches in solving complex stringology problems in computational biology.

Related Experiment Videos