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

Simulated annealing algorithm for the multiple sequence alignment problem: the approach of polymers in a random

M Hernández-Guía1, R Mulet, S Rodríguez-Pérez

  • 1Henri-Poincaré Group of Complex Systems, Physics Faculty, University of Havana, La Habana, CP 10400, Cuba.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 26, 2005
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

Evolutionary emergent metabolic interactions in cell cultures: A statistical mechanics point of view.

Physical review. E·2025
Same author

From random point processes to hierarchical cavity master equations for stochastic dynamics of disordered systems in random graphs: Ising models and epidemics.

Physical review. E·2021
Same author

Photodynamic therapy: Toward a systemic computational model.

Journal of photochemistry and photobiology. B, Biology·2018
Same author

In silico modelling of apoptosis induced by photodynamic therapy.

Journal of theoretical biology·2017
Same author

Cavity master equation for the continuous time dynamics of discrete-spin models.

Physical review. E·2017
Same author

Influence of different anoxic time exposures on active biomass, protozoa and filamentous bacteria in activated sludge.

Water science and technology : a journal of the International Association on Water Pollution Research·2016

We introduce a novel probabilistic algorithm for multiple sequence alignment using simulated annealing. This method efficiently handles gaps and converges to accurate alignments, even for large datasets where other methods fail.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Development

Background:

  • Multiple Sequence Alignment (MSA) is crucial for understanding protein evolution and function.
  • Existing probabilistic algorithms for MSA can be computationally intensive and struggle with large numbers of sequences.
  • The representation of MSA as a D-dimensional polymer offers a novel perspective for algorithmic development.

Purpose of the Study:

  • To develop a novel probabilistic algorithm for solving the multiple sequence alignment problem.
  • To improve the efficiency and accuracy of MSA, particularly for a high number of sequences (D>3).
  • To analyze the solution space of MSA and identify potential error sources in existing progressive algorithms.

Main Methods:

  • A simulated annealing probabilistic algorithm is proposed.

Related Experiment Videos

  • The algorithm represents multiple alignments as directed polymers in D dimensions.
  • Local moves are used to track alignment evolution with low computational cost, allowing gap creation/deletion without extra cost.

    • Main Results:

    • The algorithm demonstrates consistency with complete algorithms for D=3.
    • For D>3, where complete algorithms fail, the proposed method converges to reasonable alignments.
    • Analysis of the solution space reveals organizational patterns dependent on the number of sequences, suggesting limitations of progressive algorithms.
    • The algorithm outperforms progressive algorithms on artificially generated sequences and improves their results when used as an initial condition.

    Conclusions:

    • The developed simulated annealing algorithm offers an efficient and effective approach to multiple sequence alignment.
    • This method provides accurate alignments for large datasets and offers insights into MSA solution spaces.
    • The algorithm has the potential to enhance biological relevance and accuracy in sequence alignment tasks.