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

Fast, optimal alignment of three sequences using linear gap costs.

D R Powell1, L Allison, T I Dix

  • 1School of Computer Science and Software Engineering, Monash University, Australia.

Journal of Theoretical Biology
|November 18, 2000
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

Bacteriological Survey of Fresh Minced Beef on Sale at Retail Outlets in Scotland in 2019: Three Foodborne Pathogens, Hygiene Process Indicators, and Phenotypic Antimicrobial Resistance.

Journal of food protection·2022
Same author

Detailed hair shaft analysis in a man with delayed-onset Chediak-Higashi syndrome.

The British journal of dermatology·2019
Same author

Outbreak of Escherichia coli O157 Phage Type 32 linked to the consumption of venison products.

Epidemiology and infection·2018
Same author

Galactic Cosmic Radiation Induces Persistent Epigenome Alterations Relevant to Human Lung Cancer.

Scientific reports·2018
Same author

Over or under: hydride attack at the metal versus the coordinated nitrosyl ligand in ferric nitrosyl porphyrins.

Dalton transactions (Cambridge, England : 2003)·2016
Same author

Dentin Dysplasia in Notum Knockout Mice.

Veterinary pathology·2016
Same journal

An integrative model of FGF2-induced signaling and muscle cell proliferation.

Journal of theoretical biology·2026
Same journal

A Hybrid Reaction-Diffusion and Mechanical Stimulus Model for Mandibular Bone Remodeling under Chewing and Vibratory Loading.

Journal of theoretical biology·2026
Same journal

Integrated tick management strategies in fragmented peridomestic environments.

Journal of theoretical biology·2026
Same journal

Joint likelihood-free inference of the number of selected single nucleotide polymorphisms and their selection coefficients in an evolving population.

Journal of theoretical biology·2026
Same journal

Misspecification of the generation time distribution and its impact on R<sub>t</sub> estimates in structured populations.

Journal of theoretical biology·2026
Same journal

Stability-driven assembly meets Prigoginian informational dissipation. A mean-field ODE comment of entropy reduction and emergent proto-self.

Journal of theoretical biology·2026
See all related articles

This study introduces a novel algorithm for optimal three-sequence alignment using linear gap costs. It efficiently finds the best alignment, improving upon existing methods for biological sequence analysis.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Sequence Analysis

Background:

  • Traditional alignment algorithms use fixed costs, leading to suboptimal alignments with many small gaps.
  • Biological sequences often exhibit fewer, longer gaps, making linear gap cost models more biologically plausible.
  • Aligning multiple sequences (k-sequences) enhances inference reliability but poses computational challenges.

Purpose of the Study:

  • To develop an algorithm for optimal alignment of three biological sequences using linear gap costs.
  • To provide a computationally efficient alternative to the dynamic programming approach for three-sequence alignment.
  • To improve the accuracy and speed of inferring relationships between biological sequences.

Main Methods:

  • Developed a new algorithm guaranteeing optimal alignment for three sequences with linear gap costs.

Related Experiment Videos

  • Employed a speed-up technique inspired by Ukkonen's greedy algorithm for two-sequence alignment.
  • Algorithm performance is compared against standard dynamic programming methods.

    • Main Results:

    • The new algorithm achieves the same optimal alignment results as dynamic programming for three sequences.
    • Demonstrates significantly faster execution times compared to the dynamic programming approach, especially for small edit distances.
    • Provides a practical solution for computationally intensive three-sequence alignment problems.

    Conclusions:

    • The presented algorithm offers an efficient and optimal solution for three-sequence alignment with linear gap costs.
    • This method enhances the feasibility of accurate biological sequence relationship inference.
    • The algorithm represents a significant advancement in computational bioinformatics tools.