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

Using sequence compression to speedup probabilistic profile matching.

Valerio Freschi1, Alessandro Bogliolo

  • 1Information Science and Technology Institute, University of Urbino, 61029 Urbino, Italy.

Bioinformatics (Oxford, England)
|February 17, 2005
PubMed
Summary

This study introduces string compression techniques to accelerate biological sequence matching against probabilistic profiles. Algorithms based on run-length and LZ78 encoding significantly reduce computational complexity for faster sequence analysis.

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

Medical-informed machine learning: integrating prior knowledge into medical decision systems.

BMC medical informatics and decision making·2024
Same author

Exploring machine learning for untargeted metabolomics using molecular fingerprints.

Computer methods and programs in biomedicine·2024
Same author

Nrf2-Mediated Pathway Activated by <i>Prunus spinosa</i> L. (Rosaceae) Fruit Extract: Bioinformatics Analyses and Experimental Validation.

Nutrients·2023
Same author

Topological network features determine convergence rate of distributed average algorithms.

Scientific reports·2022
Same author

Exploring Artificial Neural Networks Efficiency in Tiny Wearable Devices for Human Activity Recognition.

Sensors (Basel, Switzerland)·2022
Same author

A Study on the Influence of Speed on Road Roughness Sensing: The SmartRoadSense Case.

Sensors (Basel, Switzerland)·2017

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genomics

Background:

  • Biological sequence matching against probabilistic profiles is a fundamental task in computational biology.
  • Probabilistic profiles, using scoring matrices, better capture sequence family characteristics than deterministic patterns.
  • Brute-force algorithms for this task have a time complexity of O(NP).

Purpose of the Study:

  • To enhance the efficiency of brute-force profile matching algorithms.
  • To leverage string compression techniques for computational speedup in sequence analysis.

Main Methods:

  • Exploitation of string compression techniques, specifically run-length and LZ78 encodings.
  • Development of two novel algorithms based on these compression methods.

Related Experiment Videos

Main Results:

  • Achieved significant reduction in computational complexity for profile matching.
  • The speedup achieved is directly proportional to the compression factor of the encoding used.
  • Demonstrated the practical application of compression in accelerating bioinformatics algorithms.

Conclusions:

  • String compression techniques offer a viable and effective method to speed up biological sequence profile matching.
  • The proposed algorithms provide a more efficient alternative to traditional brute-force approaches.
  • This work contributes to faster and more scalable sequence analysis in bioinformatics.