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

A fast algorithm for the optimal alignment of three strings

L Allison1

  • 1Department of Computer Science, Monash University, Australia.

Journal of Theoretical Biology
|September 21, 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

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

Inter-laboratory comparison of multi-locus variable-number tandem repeat analysis (MLVA) for verocytotoxin-producing Escherichia coli O157 to facilitate data sharing.

Epidemiology and infection·2014
Same author

VTEC infections and livestock-related exposures in Scotland, 2004.

Euro surveillance : bulletin Europeen sur les maladies transmissibles = European communicable disease bulletin·2006
Same author

Evaluation of the Escherichia coli threonine deaminase gene as a selectable marker for plant transformation.

Planta·2003
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 extends pairwise string alignment to three strings, offering an efficient algorithm for optimal three-way alignment. The method is particularly effective for similar strings, aiding evolutionary tree reconstruction.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithmic Science

Background:

  • Pairwise string alignment is a fundamental problem in bioinformatics.
  • Ukkonen's algorithm provides an efficient solution for pairwise string alignment.
  • Optimal alignment of multiple strings is crucial for evolutionary studies.

Purpose of the Study:

  • To extend Ukkonen's pairwise string alignment technique to efficiently align three strings.
  • To develop an algorithm for optimal three-way string alignment with practical performance benefits.

Main Methods:

  • Extension of Ukkonen's pairwise string alignment algorithm.
  • Development of an algorithm with O(nd2) worst-case time-complexity and O(d3) space-complexity.
  • Analysis of practical performance, often achieving O(n + d3) time.

Related Experiment Videos

Main Results:

  • An efficient algorithm for optimal three-way string alignment is presented.
  • The algorithm demonstrates superior performance when input strings are similar (d << n).
  • The method's time complexity is significantly reduced in practice.

Conclusions:

  • The developed algorithm provides an effective solution for three-way string alignment.
  • This technique can be integrated into heuristic multiple-alignment programs for more than three strings.
  • The algorithm contributes to advancements in computational evolutionary biology and sequence analysis.