Related Experiment Video
Updated: Jun 6, 2026
10:58
Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
Published on: July 25, 2013
Finding significant matches of position weight matrices in linear time
Cinzia Pizzi1, Pasi Rastas, Esko Ukkonen
1Department of Information Engineering, Università degli Studi di Padova, via Gradenigo 6/b, 35131 Padova, Italy. cinzia.pizzi@dei.unipd.it
IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 13, 2010
Summary
We developed fast algorithms for finding biological sequence motifs using position weight matrices. Our multiple-matrix filtration method significantly speeds up motif discovery in large databases like the human genome.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Position weight matrices (PWMs) are crucial for identifying functional sites in DNA and protein sequences.
- Current methods for matching PWMs can be computationally intensive, especially for large biological sequence databases.
Purpose of the Study:
- To develop and evaluate fast, online algorithms for identifying significant matches of position weight matrices.
- To generalize combinatorial string matching techniques for efficient PWM matching.
Main Methods:
- Development of novel online algorithms for weight matrix matching.
- Implementation of multiple matrix extensions for simultaneous searching.
- Comparison against brute-force and existing online/index-based algorithms.
Main Results:
- Algorithms achieve speedups proportional to matrix length (m) compared to brute-force O(mn).
- The multiple-matrix filtration algorithm demonstrated superior performance in experimental evaluations.
- Significant matches (p = 0.0001) for 123 JASPAR matrices in the human genome were found in approximately 18 minutes on a standard PC.
Conclusions:
- The developed algorithms offer significant speed improvements for motif discovery using PWMs.
- The multiple-matrix filtration approach is highly effective for large-scale genomic sequence analysis.
- These methods enhance the efficiency of identifying functional elements in biological sequences.
Related Concept Videos
01:09Wilcoxon Signed-Ranks Test for Matched Pairs
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
01:21Linear Approximation in Time Domain
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
00:57Weighted Mean
While taking the arithmetic, geometric, or harmonic mean of a sample data set, equal importance is assigned to all the data points. However, all the values may not always be equally important in some data sets. An intrinsic bias might make it more important to give more weightage to specific values over others.
For example, consider the number of goals scored in the matches of a tournament. While computing the average number of goals scored in the tournament, it may be more important to...
For example, consider the number of goals scored in the matches of a tournament. While computing the average number of goals scored in the tournament, it may be more important to...
01:30Gaussian Elimination: Problem Solving
Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...
01:23Linear time-invariant Systems
A system is linear if it displays the characteristics of homogeneity and additivity, together termed the superposition property. This principle is fundamental in all linear systems. Linear time-invariant (LTI) systems include systems with linear elements and constant parameters.
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be calculated...
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be calculated...
01:17Sign Test for Matched Pairs
The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in value between...
To conduct the sign test, we first calculate the differences in value between...