Performing Selection on a Monotonic Function in Lieu of Sorting Using Layer-Ordered Heaps
Performing Selection on a Monotonic Function in Lieu of Sorting Using Layer-Ordered Heaps
复制标题
使用层序堆对单调函数执行选择来代替排序
DOI：
10.1021/acs.jproteome.0c00711
复制
发表时间：
2021
影响因子：
4.4
通讯作者：
Serang, Oliver
中科院分区：
文献类型：
--
作者：
Lucke, Kyle;Pennington, Jake;Kreitzberg, Patrick;Serang, Oliver
非参数统计检验是不同领域的科学实验的组成部分。在执行这类测试时，对值进行排序是标准的；然而，这需要Ω(n log(N))时间来对值进行排序。因此，在给定足够的数据的情况下，即使使用非常优化的实现(如C++标准库例程std：：Sort)，排序也会成为计算瓶颈。通常，非参数统计检验仅用于按排序划分阈值之上和之下的值，其中阈值对应于显著的统计结果。不能直接使用线性时间选择和划分算法，因为选择和划分是对变换的统计显著值而不是对排序的统计执行的。通常，那些经变换的统计显著值(例如，调查家庭错误率时的p值和调查错误发现率(FDR)时的q值)只能在阈值下计算。由于该阈值未知，因此需要对数据进行排序。按层排序的堆可以在Ino(N)中构造，只能对值进行部分排序，因此可以用来绕过完全排序所需的运行时速度。这里，我们介绍了一种基于层排序的方法，用于对转换的值(例如，pValue或qValue)进行选择和划分。我们演示了使用这种方法来使用FDR阈值来划分多肽。这种方法被应用于加速Percolator，这是一种后处理算法，用于基于质谱学的蛋白质组学来评估肽谱匹配(PSM)的质量，在包含1亿PSM的数据集上提高了70%。
Nonparametric statistical tests are an integral part of scientific experiments in a diverse range of fields. When performing such tests, it is standard to sort values; however, this requires Ω(n log(n)) time to sortnvalues. Thus given enough data, sorting becomes the computational bottleneck, even with very optimized implementations such as the C++ standard library routine, std::sort. Frequently, a nonparametric statistical test is only used to partition values above and below a threshold in the sorted ordering, where the threshold corresponds to a significant statistical result. Linear-time selection and partitioning algorithms cannot be directly used because the selection and partitioning are performed on the transformed statistical significance values rather than on the sorted statistics. Usually, those transformed statistical significance values (e.g., thepvalue when investigating the family-wise error rate andqvalues when investigating the false discovery rate (FDR)) can only be computed at a threshold. Because this threshold is unknown, this leads to sorting the data. Layer-ordered heaps, which can be constructed inO(n), only partially sort values and thus can be used to get around the slow runtime required to fully sort. Here we introduce a layer-ordering-based method for selection and partitioning on the transformed values (e.g.,pvalues orqvalues). We demonstrate the use of this method to partition peptides using an FDR threshold. This approach is applied to speed up Percolator, a postprocessing algorithm used in mass-spectrometry-based proteomics to evaluate the quality of peptide-spectrum matches (PSMs), by >70% on data sets with 100 million PSMs.