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

An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees.

G A Lunter1, I Miklós, Y S Song

  • 1Department of Statistics, University of Oxford, Oxford, OX1 3TG, UK. lunter@stats.ox.ac.uk

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|February 26, 2004
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

First Measurement of Time-Dependent CP Violation in the Flavor-Changing Neutral-Current Decay B^{0}→K_{S}^{0}μ^{+}μ^{-}.

Physical review letters·2026
Same author

Measurement of the Top-Quark Production Cross Section and Charge Asymmetry at LHCb.

Physical review letters·2026
Same author

Searches for B^{0}→K^{+}π^{-}τ^{+}τ^{-} and B_{s}^{0}→K^{+}K^{-}τ^{+}τ^{-} Decays.

Physical review letters·2026
Same author

First Evidence of the B_{s}^{0}→K^{-}π^{+}γ Decay.

Physical review letters·2026
Same author

Precision Measurement of CP Violation and Branching Fractions in B^{±}→K_{S}^{0}h^{±} (h=π, K) Decays and Search for the Rare Decay B_{c}^{±}→K_{S}^{0}K^{±}.

Physical review letters·2026
Same author

First Observation of the B[over ¯]_{s}^{0}→Λ_{c}^{+}Λ[over ¯]_{c}^{-} Decay and Evidence for the B[over ¯]^{0}→Λ_{c}^{+}Λ[over ¯]_{c}^{-} Decay.

Physical review letters·2026
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

We developed an efficient algorithm for statistical multiple alignment using the TKF91 model. This method significantly improves computational efficiency for phylogenetic trees with multiple leaves.

Area of Science:

  • Computational biology
  • Bioinformatics
  • Evolutionary genetics

Background:

  • Statistical multiple sequence alignment is crucial for understanding evolutionary relationships.
  • Existing algorithms based on hidden Markov models (HMMs) for the TKF91 model face computational challenges with increasing numbers of sequences (k-leaved phylogenetic trees).

Purpose of the Study:

  • To present a novel, computationally efficient algorithm for statistical multiple alignment under the TKF91 model.
  • To overcome the limitations of existing HMM-based approaches for phylogenetic trees with arbitrary k leaves.

Main Methods:

  • Developed a combinatorial algorithm utilizing inclusion/exclusion principles.
  • Successfully eliminated the need for explicit state summation inherent in HMMs.
  • Achieved a reduced time complexity of O(2^k L^k) compared to previous O(5^k L^k) methods.

Related Experiment Videos

Main Results:

  • The new algorithm demonstrates a significant improvement in time complexity from O(5^k L^k) to O(2^k L^k).
  • Memory requirements are substantially reduced, making the method more practical.
  • The algorithm enables practical statistical multiple alignment for TKF91 models on trees with a modest number of leaves.

Conclusions:

  • The proposed combinatorial algorithm offers a more efficient and practical approach to statistical multiple alignment under the TKF91 model.
  • This advancement facilitates deeper insights into evolutionary processes using sequence data from phylogenetic trees.
  • The improved computational performance opens new avenues for large-scale phylogenetic analyses.