Chemfp项目：销售自由软件的问题

Chemfp项目有四个主要目标：(1)促进FPS格式成为密集二进制化学信息指纹的基于文本的交换格式，(2)开发BitBound算法的高性能实现，可用作新的相似性搜索实现的有效基准，(3)试验通过商业销售为一个纯粹的开放源码软件项目提供资金，以及(4)发布结果和经验教训，作为未来实施人员的指南。FPS格式只取得了很小的成功，尽管它确实影响了fpb二进制格式的开发，fpb二进制格式加载更快，但是更复杂。对两者进行了总结。建议将Chemfp基准测试和免费/开源版本的Chemfp作为参考基线，以评估其他相似性搜索工具的有效性。它们被用来评估速度更快的Chemfp商用版，它可以在标准x86-64服务器机器的单个内核上每秒测试1.3亿个1024位指纹TAnimotos。当与位边界算法相结合时，对 = 24的180万个2048位摩根指纹的k-ChEMBL1000近邻搜索平均为27毫秒/查询。9.7亿个PubChem指纹的相同搜索平均为220ms/query，使Chemfp成为最快的基于CPU的相似性搜索实现之一。现代CPU速度足够快，内存带宽和延迟现在是重要因素。单线程搜索使用了大部分可用内存带宽。根据Popcount对指纹进行排序提高了存储一致性，当与4个OpenMP线程相结合时，可以在大约30分钟内构建1百万个指纹的N × N相似度矩阵。这些观察结果可能会影响对以前的出版物的解释，以前的出版物假设搜索是强烈受CPU限制的。Chemfp项目的资金来自销售一个纯粹的开源软件产品。已经尝试了几种产品商业模式，但没有一种被证明是可持续的。讨论了一些经验，以便为正在进行的关于开放源码软件在化学信息学中的作用的对话做出贡献。

分子相似性搜索是化学信息学中的一个基本概念。最常见的形式几乎肯定是位串指纹的田本相似性搜索。许多供应商都提供完整的搜索系统，或者一个优秀的程序员可以在几个小时内实现一个具有合理搜索性能的基本系统。结合快速人口计数评估和剪枝算法的高性能搜索系统需要更多的开发工作。本文首先对这些方法进行了综述，其中许多方法要么在化学信息学文献中以增量的方式描述，使它们很难被发现，要么只发表在其他领域的专业文献中。

Chemfp项目开始是为了开发化学指纹事实上的文件格式。这需要考虑一下为什么这样的格式还不存在，以便了解在格式开发过程中需要关注哪些因素。开发了两种格式：基于文本的FPS交换格式，其读写简单、易于压缩，并且适用于流式工作流；以及二进制FPB应用格式，其更为复杂且需要随机访问读取，但加载时间显著缩短。

Python的Chemfp软件包包括优化的阈值和k最近的实现fps文件扫描搜索实现，用于搜索加载到内存中或从fpb文件的内存映射的数据集的位绑定修剪方法的高度优化实现，以及用于生成N × M和N × M相似性矩阵的OpenMP并行化的位绑定方法。使用来自ChEMBL和PubChem的数据集以及Open Babel、RDKit、OpenEye和CACTVS工具包生成的指纹来评估文件格式和搜索性能。虽然这些数据集不是为直接的科学用途而设计的，但人们希望它们与一组常见的搜索任务一起，可以成为相似性搜索性能的共同基准。初步结果表明，其中两个数据集可能太稀疏，无法提供密集和稀疏搜索算法之间的有用比较。

其中一个关键结果是现代CPU速度极快。Popcount交集计算在较旧的硬件上是限制因素，现在只需要几纳秒。这明显快于从主内存读取的内存延迟时间，这意味着缓存一致性等内存访问问题已成为重要的限制因素。例如，根据POP计数对查询进行排序可以提高多查询搜索的可伸缩性，这可能是因为搜索线程具有更好的时间局部性。大多数以前关于改进修剪方法的工作没有考虑这些因素。讨论了旧出版物中使用的机器型号，以及得出结论的原因。

20世纪80年代末和90年代，随着人们探索生成、比较和聚类指纹的方法，将这一概念扩展到稀疏和计数指纹，并将指纹扩展到二维子结构之外，带来了令人难以置信的研究增长[4]。

最广泛使用的指纹是166位MACCS密钥[5]、Daylight线性指纹[6]、ECFP环形指纹[7]和881位PubChem/CACTVS密钥[8]的变体。这些是固定长度的二进制指纹，通常具有166、881、1024或2048位，并且具有足够高的位密度，使得它们最有效地表示为未压缩的位串，而不是像倒排索引这样的稀疏编码方法。这些指纹的实现可以从大量工具中获得[9]。

虽然有很多方法可以比较两个指纹，但绝大多数使用田本相似性：

$$TAnimoto\Left({FP1，FP2}\Right)={{\Left|{FP1\cap FP2}\Right|}\mathord{\Left/{\vphantom{{\Left|{FP1\cap FP2}\Right|}{\Left|{FP1\Cup FP2}\Right|}}\Right。\kern-0pt}{\left|{fp1\Cup fp2}\right|}}$$。

$$popcount{{\Left({FP1\；\&；\；\；FP2}\Right)}\mathord{\Left/{\vphantom{{\Left({FP1\；\&；\；FP2}\Right)}{Popcount\Left({FP1|FP2}\Right)}}\Right。\kern-0pt}{popcount\Left({fp1|fp2}\right)}}$$。

其中“&；”和“|”表示按位二进制与或，“popcount()”表示结果子表达式中的1位数，通常称为“总体计数”。在Chemfp中，设置为0位的两个指纹的TAnimoto值为0，而其他一些工具包则具有不同的行为。

相似性搜索性能可能非常关键。人类通常认为响应时间在0.1秒以下是“瞬时的”，如果搜索耗时超过几秒[10]，就会开始失去焦点。快速搜索时间不仅对用户导向的相似性查询很重要，而且对二次查询也很重要。例如，复合数据库的Web界面可能会显示每个复合记录的页面，以及指向数据库中最相似的10个邻居的链接。此信息可以预先计算，当数据库更改足够多时，通常需要一些基础设施来计算和更新邻居列表。另一方面，如果搜索在响应时间预算内完成，则可以按需完成，这可能会简化系统设计。

很多算法都建立在相似搜索的基础上，算法的整体性能往往取决于相似搜索的性能。例如，泰勒-布丁纳聚类算法[11，12]的大部分时间花费在计算稀疏相似矩阵上。矩阵计算在指纹数量上是平方的，因此四倍的性能改进使得在相同的时间内处理两倍大的数据集成为可能。性能改进还可以实现更高效的系统体系结构；十倍的改进可能已经足够快，以至于需要计算集群的任务现在可以在一台机器上运行，同时还可以通过减少任务分区和网络通信的开销来实现额外的节省。

当所需的最小相似度足够高时，搜索[13]和聚类[14]的近似方法是可行的，这些方法具有可控的错误级别和更好的理论可伸缩性，适用于大数据集。本文主要研究二值指纹的精确识别方法。

许多人已经开发出技术来提高密集指纹的田本相似性搜索性能。虽然这些技术中的许多都是众所周知的，但它们在文献中并没有在一个地方描述，并且以前的一些论文描述了低效的实现。

一种方法是使用速度更快的硬件和多核或处理器[15]，或者使用专用硬件，如GPU[16]。本文重点介绍x86-64CPU，尽管许多技术可以移植到其他体系结构。

如果将有针对一组目标指纹的多个查询，则一种经常使用的方法预计算出每个目标指纹的Popcount。如果查询POP计数是A，而目标POP计数是B，则可以仅用交叉点POP计数重写公式1(2)：

$$TAnimoto={c\mathord{\Left/{\vPantom{c{\Left({A+B-c}\Right)}\Right。\Kern-0pt}{\Left({A+B-c}\Right)}}\，$$。

另一种方法是通过更有效地使用硬件来提高田本计算性能。许多搜索实现逐字解释等式1，并且使用集合数据类型来表示指纹，并且使用集合运算来计算TAnimoto。此方法通常使用大量临时集实例。相比之下，将指纹表示为字节串或机器字序列的实现使用较少的存储器，具有较少的存储器管理开销，并且可以利用少量的快速位和算术运算来实现等式2。

在过去的70多年里，已经开发了许多人口计数算法[17]。表1比较了几种实现的相对性能。完整细节在附加文件1中：表1和S1。

Chemfp 1.0使用查找表，如果表查找速度很快，这可能是有效的，但现代硬件有特殊的方法，即使是从二级缓存访问表数据也要快。指纹的长度通常是许多机器字，因此指纹弹出计数可以通过将每个字的弹出计数相加或扩展加法器树方法以处理多个字来计算[17，19]。

虽然这些算法可以用标准的、可移植的C代码实现，但更快的实现使用特定于处理器的硬件指令。实际上，所有现代X84-64硬件都支持POPCNT指令，该指令可以在一个机器周期内计算64位字的popcount。其他特定于CPU的技术也可用于较旧的消费者硬件[15]。也许令人惊讶的是，对于1024和2048位指纹，使用AVX2指令的POPCOUNT实现优于基于POPCNT的实现，因为Harley-Seal算法的AVX2实现可以一次获取和使用256位，同时更有效地利用指令并行性[20]。(大多数X84-64芯片上的POPCNT指令仅限于单个执行端口)。AVX-512指令集中的VPOPCNTDQ指令计算512位的POP计数，应该会更快。

指纹交叉点人口数计算通常被分解为多个字交叉点的和。一种优化方法是观察到相对稀疏指纹中的许多查询词只包含0个字符，其交集POP计数将始终为0，因此不需要评估。特定于查询的优化器还能够将多个单词评估合并到单个弹出计数中，并将一些单词弹出计数替换为简单的布尔表达式[21]。

一旦人口计数性能足够快，其他因素就变得重要起来。方程式3需要加法、减法和除法。如果将具有相同POP计数的所有目标分组在一起，则A + B项在处理该组时是恒定的，从而消除了添加的需要。

除法是一个相对昂贵的操作，如果表查找足够快，则可以用小的查找表[21]替换，或者重写为使用有理和整数运算。例如，阈值测试c/(A + B − c) ≥ 0.75可以重写为c * 4 ≥ 3 * (A + B − c)。对分组指纹的进一步改进是用与公式4中所示的最小所需弹出计数阈值进行比较来代替划分测试：

$$popcount\Left({FP1\；\&；\；FP2}\Right)\ge\Left\lceil{T\Left({A+B}\Right)}\mathord{\Left/{\vphantom{{T\Left({A+B}\Right)}{\Left({1+T}\Right)}}\Right。\kern-0pt}{\Left({1+T}\Right)}\Right\rceil$$。

这可以为每组计算一次，从而将阈值测试减少为简单的整数比较。

在某些处理器上，尤其是较旧的处理器上，未对齐的数据可能会显著减慢或导致程序崩溃，因此应该使用零填充进行内存对齐。

某些指纹长度特别常见，并且可以为每个长度编写专门的交叉点POP计数函数，并后退到通用实现。假设填充零的64位字和POPCNT指令，166位MACCS的完全展开的交叉点POP计数最多需要12条汇编指令，并且比通用循环将3个字的POP计数相加大约快40%。

整个搜索算法还可以专用于最重要的指纹大小。对内联交叉点popcount而不是调用函数指针的166位指纹的阈值搜索大约快25%，因为它没有函数调用开销，而且编译器具有更强的优化代码的能力。全内嵌AVX2搜索算法还可以对一些AVX2寄存器初始化一次，而不是针对每个交叉点Popcount初始化一次。

“屋顶模型”[22]强调了一旦人口计数性能足够快，存储器等待时间和带宽是如何成为限制因素的。在内存带宽为20 GiB/s的机器上，对100万个未压缩的1024位指纹进行全线性搜索的绝对最短时间仅为6毫秒。这将需要大约27亿条64位POPCNT指令每秒，外加评估TAnimoto的操作，这在没有高度指令并行性的3 GHz处理器上是不太可能实现的。实际上，在达到带宽限制之前就会出现内存延迟限制，因此更快的AVX2和VPOPCNTDQ实现必须使用预取来减少此开销。

最后，k最近搜索可以使用性能为O(Nlogk)的堆算法。田本分数是两个小数字的比率，以指纹中的位数为界，导致相对较少的不同值。对于较大的k值，可以使用计数排序[21]来消除O(Logk)开销。

虽然每个优化可能只会增加很小的性能改进，但总体效果是成倍增加的。

最快的计算是那些不需要做的计算。重复的指纹可以合并到单个记录中，这可以提供显著的加速比，特别是对于O(N2)个任务，如构建相似度矩阵。

许多搜索工具使用BitBound[23]来拒绝明显的不匹配。如果目标是找到与具有 _ _A的查询指纹相似的至少为t_ * ；_0的所有目标指纹，则目标指纹必须具有介于B_ * _t和B/t之间的_。后者需要较少的存储器存储和较少的存储器访问。这些界限在阈值搜索中给出了线性加速比，随着相似度的增加，界限越紧，而对于k近邻则是亚线性加速。使用Chemfp基准数据集进行的经验测试证实，在数据集中的指纹数量上，MACCS和FP2指纹的k = 1近邻搜索的比例为O(n~0.65)，而PubChem/CACTVS和摩根搜索的比例为O(n~0.8)(参见附加文件1：图S1)。

附加的修剪方法包括更清晰的M = 2界限[24]、XOR签名[25]、将界限递归应用于指纹子集[26、27、28]、树[27、29、30]和参考点[31、32]。这些论文经常演示所需的POP计数操作数量的数学减少，并经验性地测量与BitBound相比的性能改进。

最好的改进出现在高相似性(通常为0.8或更高)，而总体报告的性能有时比BitBound差，因为相似性阈值在化学上是合理的，也是常用的。当使用较低的相似阈值时，似乎不可能改进线性搜索以实现高维空间的精确相似搜索。

Chemfp项目的启动部分是为了推动FPS格式成为交换指纹数据的通用格式。有许多软件包可用并广泛分发用于处理指纹数据[9]。这些反过来又代表了正在使用的指纹软件的一小部分，其中包括个人研究软件和内部工具。然而，很少有来自不同来源的工具能够在不进行格式转换的情况下协同工作。

这应该是意想不到的，因为可互操作格式的有益网络效应通常会导致一个领域在远不到30年积极研究指纹的时间内汇聚到一种或少数几种格式上。几乎所有处理小分子的工具都支持SDF或SMILES文件格式，就像几乎所有序列分析工具都支持FASTA格式一样。

这三种格式的成功在很大程度上分别基于MACCS II[33]、Daylight[34]和Fasta[35]Soft的成功。

.