Related Experiment Video
Updated: Oct 21, 2025
11:53
Spatial Multiobjective Optimization of Agricultural Conservation Practices using a SWAT Model and an Evolutionary Algorithm
Published on: December 9, 2012
13.1K
A Review of Parallel Implementations for the Smith-Waterman Algorithm
Zeyu Xia1, Yingbo Cui2, Ang Zhang1
1School of Computer, National University of Defense Technology, Changsha, 410073, China.
Interdisciplinary Sciences, Computational Life Sciences
|September 6, 2021
Summary
This review systematically examines parallel local alignment algorithms, focusing on accelerating the Smith-Waterman algorithm for large-scale genomic comparisons. It aims to guide future research and tool development in sequence analysis.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Advances in sequencing technology have generated vast amounts of biological sequence data.
- Sequence alignment, particularly local alignment, is a fundamental task in sequence analysis.
- The Smith-Waterman algorithm is a standard for local alignment but suffers from high time complexity.
Purpose of the Study:
- To systematically review and summarize the research status of parallel local alignment algorithms.
- To analyze data layouts and performance of existing parallelization approaches for sequence alignment.
- To provide technical support for alignment tool developers and guidance for researchers.
Main Methods:
- Comprehensive literature review of parallelization strategies for the Smith-Waterman algorithm.
- Analysis of data layout techniques employed in parallel local alignment.
- Survey of performance metrics for typical sequence alignment tools.
Main Results:
- Current research on parallelizing local alignment algorithms appears unsystematic, hindering further advancements.
- Various parallelization techniques (vector, thread, process, heterogeneous) have been explored.
- Performance variations among alignment tools highlight the need for optimized approaches, especially for large-scale genomic comparisons.
Conclusions:
- A systematic understanding of parallel local alignment is crucial for efficient sequence analysis.
- Future research should focus on addressing the unsystematic nature of current parallelization efforts.
- This review offers insights into optimizing alignment tools for large-scale genomic data challenges.
Related Concept Videos
01:20Parallel Processing
370
The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...
370
01:06Parallel-axis Theorem
7.3K
The parallel-axis theorem provides a convenient and quick method of finding the moment of inertia of an object about an axis parallel to the axis passing through its center of mass. Consider a thin rod as an example. There is a striking similarity between the process of finding the moment of inertia of a thin rod about an axis through its middle, where the center of mass lies, and about an axis through its end using the conventional method. In the conventional method, the concept of linear mass...
7.3K
01:12Parallel-Axis Theorem for an Area
2.1K
The moment of inertia is a fundamental concept in mechanical engineering that plays a significant role in designing rotationally symmetric objects such as flywheels, gears, and other mechanical systems. In this context, we will discuss the moment of inertia of a flywheel rotating about its centroidal axis and how it relates to the moment of inertia about an axis parallel to it.
For a flywheel approximated as a solid disc, consider an infinitesimal differential element with an arbitrary distance...
For a flywheel approximated as a solid disc, consider an infinitesimal differential element with an arbitrary distance...
2.1K
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
132
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
132
01:12Trial and Error and Algorithm
217
A problem-solving strategy is a plan of action used to find a solution. Different strategies have distinct action plans. Trial and error involves trying different solutions until one works. For instance, to fix a broken printer, you might check ink levels, ensure the paper tray isn't jammed, and verify the printer's connection to your laptop. This method can be time-consuming but is commonly used. Thomas Edison, for example, used trial and error to find a suitable filament for the light...
217
01:17Wald-Wolfowitz Runs Test II
350
The Wald-Wolfowitz runs test, commonly referred to as the runs test, is a nonparametric test used to assess the randomness of ordered data. The test evaluates the number of runs, which are consecutive sequences of similar elements within the data. If the number of runs is significantly higher or lower than expected, the data is considered non-random, indicating a detectable pattern or structure.
For binary data, runs are identified using symbols such as + and −, or equivalently, 1s and...
For binary data, runs are identified using symbols such as + and −, or equivalently, 1s and...
350