无损的近似模式匹配:高效搜索方案的自动设计
Luca Renders1, Lore Depuydt1, Sven Rahmann2
1Internet Technology and Data Science Lab, Ghent University, Ghent, Belgium.
概括
这项研究自动化了对近似模式匹配的搜索方案的创建,大大提高了对更高错误率 (k=7) 的效率. 新的工具Columba提供了比现有方法更快,更全面的读取映射.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 算法设计 算法设计
背景情况:
- 大致的模式匹配对于序列分析至关重要,但设计高效的搜索方案以获得更高的误差公差 (k > 4) 是计算密集的.
- 当前的方法在处理模式匹配中增加的错误率时,在可扩展性和效率方面扎.
研究的目的:
- 开发一种自动化和高效的方法,用于生成无损近似模式的搜索方案,匹配最多k=7个错误.
- 介绍一个新的软件工具Columba,它实现了这些高级搜索方案,用于高性能读取映射.
主要方法:
- 集成一个贪的算法和一个新的整数线性编程 (ILP) 公式,用于自动搜索方案的设计.
- 开发了Hato,一个用于生成搜索方案的开源工具,以及Columba 1.2,一个开源无损读取映射器.
- 动态方案选择技术以进一步优化基于特定搜索模式的效率.
主要成果:
- 实现了高效的搜索方案,可检测多达k=7个错误,在理论和实践分析中表现优于现有策略.
- 科伦巴 1.2 展示了卓越的性能,绘制了10万个Illumina读数 (150 bp),k=6 在75秒内,k=7 在2.25小时内.
- 对于较高的k值,运行时间减少了高达53%,与损失工具相比,映射率高出四倍.
结论:
- 提出的基于ILP的方法和动态方案选择显著提高了近似模式匹配的效率.
- 科伦巴1.2是一个最先进的无损读取映射器,为高通量测序数据分析提供前所未有的速度和准确性.
相关概念视频
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
45
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...
45
01:21Frequency-dependent Selection
21.9K
When the fitness of a trait is influenced by how common it is (i.e., its frequency) relative to different traits within a population, this is referred to as frequency-dependent selection. Frequency-dependent selection may occur between species or within a single species. This type of selection can either be positive—with more common phenotypes having higher fitness—or negative, with rarer phenotypes conferring increased fitness.
21.9K
01:22Upsampling
209
Managing signal sampling rates is essential in digital signal processing to maintain signal integrity. A decimated signal, characterized by a reduced frequency range due to its lower sampling rate, can be upsampled by inserting zeros between each sample. This upsampling process expands the original spectrum and introduces repeated spectral replicas at intervals dictated by the new Nyquist frequency. To refine this zero-inserted sequence, it is passed through a lowpass filter with a cutoff...
209