在图表中找到最大的精确匹配
Nicola Rizzo1, Manuel Cáceres2, Veli Mäkinen2
1Department of Computer Science, University of Helsinki, Pietari Kalmin katu 5, P.O. Box 68, Helsinki, 00014, Finland. nicola.rizzo@helsinki.fi.
Algorithms for molecular biology : AMB
|March 12, 2024
概括
本研究提出了一种有效的算法,用于在标记图中找到最大精确匹配 (MEM),这对生物信息学至关重要. 新方法显著加快了弹性创始人图的对齐过程,图形MEM比字符串MEM少.
科学领域:
- 计算生物学 计算生物学
- 生物信息学算法 算法
- 图形理论 图形理论
背景情况:
- 最大精确匹配 (MEM) 是序列对齐中的重要种子.
- 在标记图中找到MEM是计算上具有挑战性的.
- 由于SETH的复杂性,现有的方法在任意图表上面临限制.
研究的目的:
- 开发一种有效的算法,用于在标记图中找到k-MEMs.
- 改善Elastic Founder Graphs上的对齐方法的种子生成.
- 分析基于图形的MEM发现的效率和适用性.
主要方法:
- 介绍了一个O{n d L + 输出时间算法,用于查找跨越L节点的k-MEM.
- 开发了一个k-MEM寻找可索引弹性创始人图形的解决方案.
- 概括了多个查询字符串的方法.
主要成果:
- 为弹性创始人图表实现了O ((H^2 log H + 输出H) 的运行时间.
- 证明图形MEM比字符串MEM少得多.
- 为开发的算法提供实验验证.
结论:
- 在弹性创始者图表上实现了对齐方法的高效种子生产.
- 促进了种子链扩展对齐在图表上的实施.
- 发布开源代码用于实际应用.
相关概念视频
Wilcoxon Signed-Ranks Test for Matched Pairs
123
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...
123
Sign Test for Matched Pairs
131
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...
To conduct the sign test, we first calculate the differences in...
131
Second Uniqueness Theorem
1.0K
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
1.0K
Quantifying and Rejecting Outliers: The Grubbs Test
1.6K
Sometimes, a data set can have a recorded numerical observation that greatly deviates from the rest of the data. Assuming that the data is normally distributed, a statistical method called the Grubbs test can be used to determine whether the observation is truly an outlier. To perform a two-tailed Grubbs test, first, calculate the absolute difference between the outlier and the mean. Then, calculate the ratio between this difference and the standard deviation of the sample. This...
1.6K
Fisher's Exact Test
503
Fisher's exact test is a statistical significance test widely used to analyze 2x2 contingency tables, particularly in situations where sample sizes are small. Unlike the chi-squared test, which approximates P-values and assumes minimum expected frequencies of at least five in each cell, Fisher's exact test calculates the exact probability (P-value) of observing the data or more extreme results under the null hypothesis. This feature makes it especially valuable when the assumptions of...
503
Routh-Hurwitz Criterion II
246
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
246


