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...
Per-Unit Sequence Models01:26

Per-Unit Sequence Models

An ideal Y-Y transformer, grounded through neutral impedances, displays per-unit sequence networks akin to those of a single-phase ideal transformer when subjected to balanced positive- or negative-sequence currents. These currents do not produce neutral currents, and their associated voltage drops.
Zero-sequence currents, which are identical in magnitude and phase, generate a neutral current, resulting in voltage drops across the neutral impedance and the low-voltage winding. If the...
Cis-regulatory Sequences02:02

Cis-regulatory Sequences

Cis-regulatory sequences are short fragments of non-coding DNA that are present on the same chromosomes as the genes that they regulate. These fragments serve as binding sites for transcriptional regulators, proteins that are responsible for controlling gene transcription and differential gene expression across cell types in eukaryotes. Cis-regulatory sequences can be close to the gene of interest or thousands of bases away in the DNA sequence; however, those sequences that are further away are...
Cis-regulatory Sequences02:02

Cis-regulatory Sequences

Cis-regulatory sequences are short fragments of non-coding DNA that are present on the same chromosomes as the genes that they regulate. These fragments serve as binding sites for transcriptional regulators, proteins that are responsible for controlling gene transcription and differential gene expression across cell types in eukaryotes. Cis-regulatory sequences can be close to the gene of interest or thousands of bases away in the DNA sequence; however, those sequences that are further away are...
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...
Sequences01:29

Sequences

Sequences are fundamental mathematical objects consisting of ordered lists of numbers that follow a specific rule or pattern. Sequences are critical in various mathematical concepts, including calculus, series, and number theory. They can model real-world phenomena such as population growth, financial investments, and physical processes like the diminishing height of a bouncing ball.Each number in a sequence is referred to as a term. Typically, the terms are denoted as a1, a2, a3,…, where the...

You might also read

Related Articles

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

Sort by
Same author

Efficient and robust search of microbial genomes via phylogenetic compression.

Nature methods·2025
Same author

New algorithms for structure informed genome rearrangement.

Algorithms for molecular biology : AMB·2023
Same author

Efficient and Robust Search of Microbial Genomes via Phylogenetic Compression.

bioRxiv : the preprint server for biology·2023
Same author

Predicting the pathogenicity of bacterial genomes using widely spread protein families.

BMC bioinformatics·2022
Same author

Space-efficient representation of genomic k-mer count tables.

Algorithms for molecular biology : AMB·2022
Same author

Set-Min Sketch: A Probabilistic Map for Power-Law Distributions with Application to <i>k</i>-Mer Annotation.

Journal of computational biology : a journal of computational molecular cell biology·2022
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

Related Experiment Video

Updated: Jun 2, 2026

Exploring Sequence Space to Identify Binding Sites for Regulatory RNA-Binding Proteins
11:34

Exploring Sequence Space to Identify Binding Sites for Regulatory RNA-Binding Proteins

Published on: August 9, 2019

Regular language constrained sequence alignment revisited.

Gregory Kucherov1, Tamar Pinhas, Michal Ziv-Ukelson

  • 1LIFL/CNRS and INRIA Lille Nord-Europe, Villeneuve d'Ascq, France.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|May 11, 2011
PubMed
Summary
This summary is machine-generated.

This study accelerates regular language constrained sequence alignment algorithms, improving efficiency for incorporating prior knowledge into sequence analysis. The enhanced methods reduce computational complexity, making them faster for practical applications.

More Related Videos

An Integrated Approach for Microprotein Identification and Sequence Analysis
09:37

An Integrated Approach for Microprotein Identification and Sequence Analysis

Published on: July 12, 2022

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

Related Experiment Videos

Last Updated: Jun 2, 2026

Exploring Sequence Space to Identify Binding Sites for Regulatory RNA-Binding Proteins
11:34

Exploring Sequence Space to Identify Binding Sites for Regulatory RNA-Binding Proteins

Published on: August 9, 2019

An Integrated Approach for Microprotein Identification and Sequence Analysis
09:37

An Integrated Approach for Microprotein Identification and Sequence Analysis

Published on: July 12, 2022

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Analysis

Background:

  • Sequence alignment is crucial for biological data analysis.
  • Incorporating a priori knowledge via finite automata or regular expressions enhances alignment accuracy.
  • Existing algorithms for Regular Expression Constrained Sequence Alignment have time complexities of O(n²t⁴) and O(n²t³).

Purpose of the Study:

  • To further accelerate algorithms for Regular Language Constrained Sequence Alignment.
  • To reduce the worst-case time complexity of these alignment procedures.
  • To investigate alternative computational approaches for efficiency.

Main Methods:

  • Optimizing the size of Straight-Line Programs for the maxima computation subproblem.
  • Applying dynamic programming with improved subproblem solutions.
  • Exploring a Steiner Tree computation-based approach.

Main Results:

  • Reduced worst-case time complexity to O(n²t³)/log t).
  • Demonstrated practical efficiency of both optimized Straight-Line Program and Steiner Tree methods.
  • Showcased particular effectiveness with dense input automata.

Conclusions:

  • The developed algorithms offer significant speedups for Regular Language Constrained Sequence Alignment.
  • Both novel approaches are computationally efficient in practice.
  • These advancements facilitate more effective incorporation of prior knowledge in sequence alignment.