在Wheeler DFAs上的计算匹配统计
Alessio Conte1, Nicola Cotumaccio2,3, Travis Gagie3
1University of Pisa, Italy.
概括
这项研究将匹配统计算法概括为从字符串到Wheeler自动机的近似字符串匹配. 它为自动机引入了最长的共同前 (LCP) 阵列,将压缩后树功能扩展到标记图形.
科学领域:
- 计算机科学 计算机科学
- 生物信息学算法 算法
- 图形理论 图形理论
背景情况:
- 在生物信息学中,近似的字符串匹配至关重要,通常使用匹配统计数据来解决.
- 现有的有效算法用于匹配统计数据,利用压缩后树和最长的共同前 (LCP) 阵列.
- 这些方法主要用于线性字符串数据结构.
研究的目的:
- 将高效匹配统计算法推广到线性字符串之外.
- 将压缩后树概念的适用性扩展到更复杂的数据结构.
- 建立在字符串匹配的背景下分析惠勒自动的基本方法.
主要方法:
- "奥勒布斯奇的概括"等人. (2010) 匹配统计学算法.
- 适应压缩后树组件,特别是LCP数组概念.
- 为惠勒决定性有限自动机开发一种新的LCP数组定义.
主要成果:
- 成功地将匹配统计计算推广到惠勒自动机.
- 对Wheeler自动机的LCP阵列概念的介绍和正式化.
- 展示了一条将后树功能扩展到标记图形的途径.
结论:
- 拟议的概括大大扩大了匹配统计的范围.
- 惠勒自动机的LCP阵列是基于图形的字符串处理的关键创新.
- 这项工作为标记图形上的高级生物信息算法提供了基础.
更多相关视频
相关概念视频
Friedman Two-way Analysis of Variance by Ranks
185
Friedman's Two-Way Analysis of Variance by Ranks is a nonparametric test designed to identify differences across multiple test attempts when traditional assumptions of normality and equal variances do not apply. Unlike conventional ANOVA, which requires normally distributed data with equal variances, Friedman's test is ideal for ordinal or non-normally distributed data, making it particularly useful for analyzing dependent samples, such as matched subjects over time or repeated measures...
185
Wilcoxon Signed-Ranks Test for Matched Pairs
119
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...
119
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
Wilcoxon Signed-Ranks Test for Median of Single Population
120
The Wilcoxon signed-rank test for the median of a single population is a nonparametric test used to evaluate whether the median of a population differs from a specified value. Unlike parametric tests, it does not require data to follow a normal distribution, making it suitable for non-normal or small samples. The test begins by calculating the difference (d) between each observation and the hypothesized median. The absolute values of these differences are ranked in ascending order, with ties...
120
Fisher's Exact Test
465
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...
465
Statistical Analysis System (SAS)
156
SAS, short for Statistical Analysis System, is a powerful data analysis, management, and visualization tool. Developed by the SAS Institute in the early 1970s, SAS has evolved into a comprehensive software suite used across various industries for statistical analysis, business intelligence, and predictive modeling.
Applications: SAS finds applications in numerous fields, including healthcare for clinical trial analysis, finance for risk assessment, marketing for customer data analysis, and...
Applications: SAS finds applications in numerous fields, including healthcare for clinical trial analysis, finance for risk assessment, marketing for customer data analysis, and...
156


