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 optimizing whole genome alignment with noise.

Prudence W H Wong1, T W Lam, N Lu

  • 1Department of Computer Science, University of Hong Kong, Hong Kong. whwong@cs.hku.hk

Bioinformatics (Oxford, England)
|May 18, 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

Search for Light Pseudoscalar Bosons, Pair-Produced in Higgs Boson Decays in the Four-Electron Final State in Proton-Proton Collisions at sqrt[s]=13  TeV.

Physical review letters·2026
Same author

First Evidence for Mixing-Induced CP Violation in B_{s}^{0}→J/ψϕ(1020) Decays in pp Collisions at sqrt[s]=13  TeV.

Physical review letters·2026
Same author

Observation of Suppressed Charged-Particle Production in Ultrarelativistic Oxygen-Oxygen Collisions.

Physical review letters·2026
Same author

Measurement of D^{0} Meson Photoproduction in Ultraperipheral Heavy Ion Collisions.

Physical review letters·2026
Same author

Observation of tWZ Production at the CMS Experiment.

Physical review letters·2026
Same author

Black Hole Spectroscopy and Tests of General Relativity with GW250114.

Physical review letters·2026
Same journal

MCFST: Spatial domain identification method based on multi-view graph convolutional network and graph fusion network.

Bioinformatics (Oxford, England)·2026
Same journal

SpaBiT: Enhancing Spatial Transcriptomics Resolution via Bidirectional Attention Transformers.

Bioinformatics (Oxford, England)·2026
Same journal

EDEL: Enhancing Dense Retrievers for Curation of Biomedical Knowledge Bases.

Bioinformatics (Oxford, England)·2026
Same journal

Informative Relational Learning for Adverse Reaction Prediction with Enhanced Generalization to Novel Drugs.

Bioinformatics (Oxford, England)·2026
Same journal

An interpretable deep learning framework uncovers features governing CRISPR-Cas9 genome-editing efficiency.

Bioinformatics (Oxford, England)·2026
Same journal

3DICE: Interpretable 3D Cross-Modal Learning for Drug-Target Interaction Prediction and Large-Scale Drug Discovery.

Bioinformatics (Oxford, England)·2026
See all related articles

This study introduces MaxMinCluster, an efficient algorithm for whole-genome alignment to find conserved genes, even with noisy data. It significantly outperforms existing tools like MUMmer in identifying gene regions.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Whole-genome alignment is crucial for identifying conserved genes.
  • Existing heuristic tools face challenges with global optimization and noise tolerance.
  • Brute-force methods for genome alignment are computationally prohibitive due to exponential time complexity with noise.

Purpose of the Study:

  • To develop an optimized algorithm for whole-genome alignment that identifies conserved genes.
  • To address the challenges of global optimization and noise tolerance in gene conservation detection.
  • To improve the efficiency and scalability of whole-genome comparison methods.

Main Methods:

  • Formulation of a novel optimization problem for uncovering conserved genes with global consideration.

Related Experiment Videos

  • Development of an algorithm, MaxMinCluster, with improved time and space complexity.
  • Implementation of MaxMinCluster leveraging reduced space requirements for practical application.

    • Main Results:

    • Achieved significant improvements in time and space complexity to O(k^2n^2) and O(k^2n) respectively, where n is input size and k is noise level.
    • MaxMinCluster successfully identified a high percentage of conserved genes in real datasets, validated against GenBank.
    • Demonstrated superior performance compared to MUMmer, a leading whole-genome alignment tool.

    Conclusions:

    • MaxMinCluster offers an efficient and effective solution for whole-genome alignment and conserved gene discovery.
    • The algorithm's performance and scalability make it suitable for large-scale genomic analyses.
    • The developed approach provides a valuable tool for comparative genomics research.