FORAlign:使用基于四个俄罗斯人的方法的FOR-blocks加快差距相似DNA双向序列对齐,具有线性空间复杂性的方法
Yanming Wei1,2, Tong Zhou2,3, Yixiao Zhai2,3
1School of Computer Science and Technology, No. 266, Xinglong Section of Xifeng Road, Chang'an Zone, Xidian University, Xi'an 710126, China.
Briefings in bioinformatics
|February 23, 2025
概括
FORAlign使用四个俄国人的算法加速双向序列对齐 (PSA),实现了低相似度序列的显著加速度. 这种生物信息学工具增强了遗传学分析和多重序列对齐能力.
科学领域:
- 计算型生物信息学 计算型生物信息学
- 生物信息学算法 算法
- 序列分析 序列分析
背景情况:
- 配对序列对齐 (PSA) 是生物信息学任务的基础,如多个序列对齐和遗传学分析.
- 现有的方法,如尼德尔曼-温斯 (Needleman-Wunsch),可能是计算密集的,特别是在相似性较低的序列中.
- 加快PSA对于推进大规模生物数据分析至关重要.
研究的目的:
- 介绍 FORAlign 算法,用于加速双向序列对齐.
- 评估FORAlign的性能与已建立的方法相比,特别是对于相似性较低的序列.
- 为PSA和下游生物信息学应用提供一个实用的库.
主要方法:
- 开发了FORAlign算法,适应了PSA的四个俄罗斯算法.
- 实现了与平行加速的希尔施伯格算法相同的上限时间和空间复杂性.
- 实现了FORAlign作为一个支持PSA的库,多个序列对齐和家族遗传树构建.
主要成果:
- 与尼德尔曼-温施方法相比,FORAlign在低相似性序列中显示出高达16.79倍的速度.
- 经验评估表明,FORAlign在低相似性PSA任务中优于现有的波浪阵线对齐 (WFA) 软件.
- 该算法成功地使用非启发式方法对准了麻疹序列.
结论:
- FORAlign在加速对对顺序对齐方面取得了重大进展,特别是在挑战低相似度数据集时.
- FORAlign图书馆为计算生物信息学研究提供了一个有价值的,免费可用的工具.
- 这项工作有助于更有效的遗传学分析和多重序列对齐.
相关概念视频
02:27DNA Base Pairing
26.8K
26.8K
01:05Maxam-Gilbert Sequencing
10.9K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
10.9K
02:04Fixing Double-strand Breaks
3.1K
3.1K
01:57Sanger Sequencing
752.3K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
752.3K
03:21RNA-seq
9.8K
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
9.8K
03:00Next-generation Sequencing
87.0K
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
87.0K