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 Concept Videos

Maxam-Gilbert Sequencing01:05

Maxam-Gilbert Sequencing

In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Multi-species Conserved Sequences02:51

Multi-species Conserved Sequences

Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale  studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Prismatic Beams: Problem Solving01:15

Prismatic Beams: Problem Solving

In the design of a supported timber beam subjected to a distributed load, both the beam's physical dimensions and the timber's characteristics, such as its grade and species, are critical. These factors determine the allowable stress values, which are crucial for calculating the necessary beam depth to ensure structural integrity and safety.
The design begins with analyzing the beam as a free body to identify moments and force balances, thereby determining support reactions. Next, the designer...
Shearing Stresses in a Beam: Problem Solving01:14

Shearing Stresses in a Beam: Problem Solving

A cantilever beam with a rectangular cross-section under distributed and point loads experiences shearing stresses. The analysis begins by identifying the loads acting on the beam. Then, the reactions at the beam's fixed end are calculated using equilibrium equations. The vertical reaction is a combination of the distributed and point loads, while the moment reaction is the sum of their moments. The shear force distribution along the beam, resulting from these loads, is established by creating...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

On the hybridization of memetic algorithms with branch-and-bound techniques.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2007
Same journal

Analysis of strength degradation of coal and rock masses and stability of mined areas under long term immersion environment.

PloS one·2026
Same journal

Biogenic Silver-Selenium nanocomposite with anticancer activity and potent efficacy against vancomycin-resistant Staphylococcus aureus.

PloS one·2026
Same journal

Preparation and physicochemical characterization of a biodegradable chitosan/carboxymethyl cellulose hydrogel synthesized in NaOH/urea medium.

PloS one·2026
Same journal

Action-guilt, survivor-guilt, and depression in combat-related PTSD.

PloS one·2026
Same journal

Explainable machine learning for predicting activities of daily living at discharge in stroke patients: A retrospective study using SHAP interpretability.

PloS one·2026
Same journal

Deep learning based two-way feature depiction model for brain tumor detection.

PloS one·2026
See all related articles

Related Experiment Video

Updated: May 15, 2026

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

A multilevel probabilistic beam search algorithm for the shortest common supersequence problem.

José E Gallardo1

  • 1Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Málaga, Spain. pepeg@lcc.uma.es

Plos One
|January 10, 2013
PubMed
Summary
This summary is machine-generated.

This study introduces a novel heuristic for the shortest common supersequence problem, offering improved solutions for bioinformatics and AI applications. The probabilistic Beam Search variant delivers high-quality results efficiently for most problem sizes.

More Related Videos

A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types
12:39

A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types

Published on: December 10, 2012

Novel Sequence Discovery by Subtractive Genomics
09:40

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

Related Experiment Videos

Last Updated: May 15, 2026

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types
12:39

A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types

Published on: December 10, 2012

Novel Sequence Discovery by Subtractive Genomics
09:40

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

Area of Science:

  • Bioinformatics
  • Artificial Intelligence
  • Computer Science

Background:

  • The shortest common supersequence (SCS) problem is a fundamental computational challenge with broad applications.
  • Its NP-hard nature necessitates heuristic approaches over exact methods for efficient solutions.
  • Existing methods struggle with large-scale SCS instances.

Purpose of the Study:

  • To develop an effective heuristic for the shortest common supersequence problem.
  • To improve solution quality and efficiency compared to current state-of-the-art algorithms.
  • To address the computational challenges posed by NP-hard problems in bioinformatics and AI.

Main Methods:

  • A novel heuristic algorithm based on a probabilistic variant of Beam Search is proposed.
  • The algorithm is applied at multiple levels to enhance its performance.
  • Empirical analysis and comparison with existing literature approaches were conducted.

Main Results:

  • The proposed heuristic demonstrates superior solution quality for medium and large SCS instances.
  • It achieves these results within a reasonable computational time frame.
  • For very large instances, the heuristic still provides better solutions, though execution time increases.

Conclusions:

  • The probabilistic Beam Search heuristic offers a promising approach to solving the SCS problem.
  • It provides a practical and efficient method for tackling complex instances in bioinformatics and AI.
  • Further research may explore optimizations for extremely large datasets.