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

Constrained sequence alignment

K M Chao1, R C Hardison, W Miller

  • 1Department of Computer Science, The Pennsylvania State University, University Park, 16802, U.S.A.

Bulletin of Mathematical Biology
|May 1, 1993
PubMed
Summary
This summary is machine-generated.

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

Achievement of Target Gain Larger than Unity in an Inertial Fusion Experiment.

Physical review letters·2024
Same author

Lawson Criterion for Ignition Exceeded in an Inertial Fusion Experiment.

Physical review letters·2022
Same author

Letter from New York-Yellow Fever Prevented by Innoculation.

The Southern medical record·2022
Same author

Scintillation light detection in the 6-m drift-length ProtoDUNE Dual Phase liquid argon TPC.

The European physical journal. C, Particles and fields·2022
Same author

Prospects for beyond the Standard Model physics searches at the Deep Underground Neutrino Experiment: DUNE Collaboration.

The European physical journal. C, Particles and fields·2021
Same author

STAGdb: a 30K SNP genotyping array and Science Gateway for Acropora corals and their dinoflagellate symbionts.

Scientific reports·2020
Same journal

Effects of Seasonal Births and Predation on Disease Spread.

Bulletin of mathematical biology·2026
Same journal

Identifiability, Sensitivity, and Genetic Algorithms in Bacterial Biofilm Selection Models.

Bulletin of mathematical biology·2026
Same journal

Slow Evolution Towards Generalism in a Model of Variable Dietary Range.

Bulletin of mathematical biology·2026
Same journal

CBINN: Cancer Biology-Informed Neural Network for Unknown Parameter Estimation and Missing Physics Identification.

Bulletin of mathematical biology·2026
Same journal

A Cost-Sensitive Behavioral Modeling Analysis of the Early Identification and Control of Infectious Diseases.

Bulletin of mathematical biology·2026
Same journal

Tracking Dynamics of Superspreading Through Contacts, Exposures, and Transmissions in Edge-Based Network Epidemics.

Bulletin of mathematical biology·2026
See all related articles

This study introduces a dynamic programming algorithm for sequence alignment with boundary constraints. The method efficiently computes alignments using affine or concave gap penalties within a feasible region.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Design

Background:

  • Sequence alignment is fundamental in bioinformatics.
  • Traditional algorithms lack efficiency for constrained alignments.
  • Dynamic programming matrices are key to sequence alignment.

Purpose of the Study:

  • To develop an efficient dynamic programming algorithm for sequence alignment.
  • To incorporate arbitrary boundary line constraints into the alignment process.
  • To analyze the computational complexity for different gap penalty types.

Main Methods:

  • Developed a dynamic programming algorithm.
  • Implemented constraints using arbitrary boundary lines in the matrix.
  • Analyzed time and space complexity for affine and concave gap penalties.

Related Experiment Videos

Main Results:

  • The algorithm achieves O(F) computation time and O(M+N) space for affine gap penalties, where F is the feasible region area.
  • The approach extends to concave gap penalties with manageable increases in complexity.
  • Efficiently handles sequence alignments within defined matrix boundaries.

Conclusions:

  • The proposed algorithm offers significant efficiency gains for constrained sequence alignment.
  • This method provides a flexible framework for various biological sequence analysis tasks.
  • The findings contribute to optimizing computational approaches in bioinformatics.