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

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...
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...
Arithmetic Sequences01:30

Arithmetic Sequences

An arithmetic sequence is a structured arrangement of numbers where each term is derived by adding a constant value, known as the common difference, to the previous term. This consistent pattern allows for the efficient computation of any term within the sequence as well as the cumulative sum of multiple terms. The formula for finding the nth term of an arithmetic sequence is:Here, aₙ represents the nth term of the sequence, a is the first term, d is the common difference, and n is the term...
Critical Numbers and the Closed Interval Method01:21

Critical Numbers and the Closed Interval Method

Understanding the maximum and minimum values of a function is essential for analyzing its overall behavior. These values, often referred to as extrema, provide insight into how a function behaves across its domain. In mathematical terms, extrema can be either local—representing peaks and valleys within a limited region—or absolute, indicating the highest or lowest points over an entire interval.A function’s extrema occur at critical numbers, which are values in the domain where the derivative...
Geometric Sequences01:30

Geometric Sequences

In systems where values diminish by a constant proportion at each stage, the resulting sequence follows a geometric structure. Each new value in the sequence is obtained by applying a fixed multiplier to the preceding term. This regular, proportional decline type is often used to represent processes involving gradual loss, such as energy dissipation or reduction in amplitude over time.When analyzing the total effect of such a process across unlimited iterations, the series of values is referred...
The Intermediate Value Theorem01:25

The Intermediate Value Theorem

The Intermediate Value Theorem is a foundational result in calculus that guarantees the existence of solutions within certain intervals for continuous functions. Formally, the Intermediate Value Theorem states that if a function f is continuous on the closed interval [a, b], and if N is any value between f(a) and f(b), then there exists at least one c ∈ (a, b) such that f(c) = N. This theorem is instrumental in proving the existence of roots and in analyzing the behavior of continuous functions...

You might also read

Related Articles

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

Sort by
Same author

A Kernelization Algorithm for Finding a Perfect Phylogeny From Mixed Tumor Samples.

IEEE transactions on computational biology and bioinformatics·2025
Same author

Faster Algorithms for Constructing Frequency Difference Consensus Trees.

IEEE transactions on computational biology and bioinformatics·2025
Same author

Fast Algorithms for the Simplified Partial Digest Problem.

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

A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees.

IEEE/ACM transactions on computational biology and bioinformatics·2019
Same author

Fast Algorithms for Computing Path-Difference Distances.

IEEE/ACM transactions on computational biology and bioinformatics·2018
Same author

A New Efficient Algorithm for the Frequent Gene Team Problem.

IEEE/ACM transactions on computational biology and bioinformatics·2016
Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024
See all related articles

Related Experiment Video

Updated: May 30, 2026

Introductory Analysis and Validation of CUT&RUN Sequencing Data
04:58

Introductory Analysis and Validation of CUT&RUN Sequencing Data

Published on: December 13, 2024

Output-sensitive algorithms for finding the nested common intervals of two general sequences.

Biing-Feng Wang1

  • 1National Tsing Hua University, Hsinchu.

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|August 17, 2011
PubMed
Summary
This summary is machine-generated.

This study presents efficient algorithms for finding nested common intervals in biological sequences across three models: uniqueness, free-inclusion, and bijection. The algorithms offer improved time complexity for identifying these intervals and their approximate versions.

More Related Videos

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
10:36

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Published on: August 3, 2018

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: May 30, 2026

Introductory Analysis and Validation of CUT&RUN Sequencing Data
04:58

Introductory Analysis and Validation of CUT&RUN Sequencing Data

Published on: December 13, 2024

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
10:36

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Published on: August 3, 2018

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
  • Sequence Analysis

Background:

  • Identifying common intervals in biological sequences is crucial for understanding gene relationships and evolutionary history.
  • Existing models (uniqueness, free-inclusion, bijection) offer different ways to define nested common intervals, each with implications for computational analysis.

Purpose of the Study:

  • To develop and analyze efficient algorithms for finding nested common intervals in two general sequences.
  • To evaluate these algorithms across three distinct models: uniqueness, free-inclusion, and bijection.
  • To investigate approximate nested common intervals within the bijection model.

Main Methods:

  • Development of time-efficient algorithms for exact nested common interval identification.
  • Analysis of algorithm performance based on sequence length (n) and output size (N(out)).
  • Introduction of an algorithm for approximate nested common intervals considering allowed gaps (δ).

Main Results:

  • Achieved O(n + N(out)) time complexity for uniqueness and bijection models.
  • Developed an O(n(1+ε) + N(out)) algorithm for the free-inclusion model.
  • Established output size upper bounds: O(n²) for uniqueness/free-inclusion and O(Cn) for bijection.
  • Presented an O(δn + N(out)) algorithm for approximate nested common intervals with N(out) = O(δn³).

Conclusions:

  • The study provides significant algorithmic improvements for finding nested common intervals in biological sequence analysis.
  • The developed algorithms are efficient and offer valuable insights into sequence comparison and evolutionary relationships.
  • The findings contribute to the advancement of computational tools for genomic research.