一个随机并行算法,有效地找到接近最佳的通用击球组
Barış Ekim1,2, Bonnie Berger1,2, Yaron Orenstein3
1Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.
概括
我们开发了PASHA,这是一个新的平行算法,用于生成通用打击集 (UHS). PASHA显著加快了大量测序数据集的处理速度,同时保持了高精度和低内存使用量.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 算法设计 算法设计
背景情况:
- 下一代测序产生大量数据,需要高效的处理算法.
- 全面打击集 (UHS) 为序列分析任务提供了对最小化器的有希望的替代方案.
- 目前的UHS计算方法对于实用,大规模的测序应用来说太慢和内存密集.
研究的目的:
- 开发一种实用,高效的算法,用于计算接近最佳的通用击球套.
- 解决现有的UHS施工方法的计算瓶问题.
- 为了使UHS在高通量序列分析中的应用成为可能.
主要方法:
- 为UHS生成开发了一个随机并行算法 (PASHA).
- 借助理论和架构技术并行-mer击中数字计算并减少内存使用.
- 应用随机的设置覆盖技术,以实现更快的通用-mer选择.
主要成果:
- 与现有的算法相比,PASHA在运行时间和内存使用方面实现了数量级的改进.
- 该算法有效地处理大值的 (例如,).
- PASHA生成了接近最佳的UHS,设置大小可以证明接近最佳,仅略大于串行确定性方法.
结论:
- PASHA 是第一个实际的,随机的并行算法,用于生成接近最佳的通用击球集.
- 开发的方法显著减少了UHS构建的运行时间和内存需求.
- 预计PASHA将在高通量序列分析管道中得到广泛采用.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
48
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...
48
Random Sampling Method
11.0K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
11.0K
Wald-Wolfowitz Runs Test II
227
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...
227
Wald-Wolfowitz Runs Test I
640
The Wald-Wolfowitz test, also known as the runs test, is a nonparametric statistical test used to assess the randomness of a sequence of two different types of elements (e.g., positive/negative values, successes/failures). It examines whether the order of the elements in a sequence is random or if there is a pattern or trend present. This nonparametric test applies to any ordered data despite the population and sample data distribution, even if a higher sample size is available.
The test works...
The test works...
640
Cluster Sampling Method
11.9K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
11.9K
Sampling Plans
180
Sampling is a crucial step in analytical chemistry, allowing researchers to collect representative data from a large population. Common sampling methods include random, judgmental, systematic, stratified, and cluster sampling.
Random sampling is a method where each member of the population has an equal chance of being selected for the sample. It involves selecting individuals randomly, often using random number generators or lottery-type methods. For example, when analyzing the properties of a...
Random sampling is a method where each member of the population has an equal chance of being selected for the sample. It involves selecting individuals randomly, often using random number generators or lottery-type methods. For example, when analyzing the properties of a...
180


