Fragment-based shape signature techniques have proven to be powerful tools for computer-aided drug design. They allow scientists to search for target molecules with some similarity to a known active compound. They do not require reference to the full underlying chemical structure, which is essential to deal with chemical databases containing millions of compounds. However, finding the optimal match of a part of the fragmented compound can be time-consuming. In this paper, we use constraint programming to solve this specific problem. It involves finding a weighted assignment of fragments subject to connectivity constraints. Our experiments demonstrate the practical relevance of our approach and open new perspectives, including generating multiple, diverse solutions. Our approach constitutes an original use of a constraint solver in a real time setting, where propagation allows to avoid an enumeration of weighted paths. The model must remain robust to the addition of constraints making some instances not tractable. This particular context requires the use of unusual criteria for the choice of the model: lightweight, standard propagation algorithms, data structures without prohibitive constant cost. The objective is not to design new, complex algorithms to solve difficult instances.
翻译:基于碎片的形状签字技术已证明是计算机辅助药物设计的有力工具,使科学家能够搜索与已知活性化合物具有某种相似性的目标分子。它们不要求提及完整的基本化学结构,这对于处理含有数以百万计化合物的化学数据库至关重要。然而,找到部分零碎化合物的最佳匹配可能是耗时的。在本文中,我们使用制约程序来解决这一具体问题。它涉及找到受连通制约的碎片的加权分配。我们的实验表明我们的方法和开放的新视角的实际相关性,包括产生多种不同的解决方案。我们的方法是在实际时间设置中最初使用一种制约解算器,在实时设置中,传播可以避免对加权路径的罗列。模型必须保持坚固,以补充使某些情况无法移动的制约。这一特定背景要求使用不寻常的标准来选择模型:轻量、标准传播算法、不需负担固定成本的数据结构。目的不是设计新的复杂算法来解决困难。