0

这个想成为生物信息学家的人需要你的帮助。下面的代码使用 rdkit 查找化合物规范微笑的相似性。经过一番研究，我明白它必须是 O(n)！（或者不是？）因为对于一个包含 944 个条目的小文件，它需要 20 分钟，而对于最大的一个，即 330.000 个条目，它已经运行了 30 多个小时。现在，我现在知道它的一个问题是它不会只比较元素一次，所以这是减慢它的一个因素。我在这里读到，您可以使用 itertools 库进行快速比较，但通常如何才能使这段代码变得更好？在我尝试学习时，任何帮助将不胜感激:)

from rdkit import Chem
from rdkit import DataStructs
from rdkit.Chem import AllChem
import pandas as pd


l =[]
s1 = []
s2 = []
d1 = []
d2 = []
with open('input_file.csv', 'r') as f:
    df = pd.read_csv(f, delimiter = ',', lineterminator = '\n', header = 0)
    for i in range(0, df.shape[0]):
        l.append(df.iloc[i, 1])


for i in range(0, df.shape[0]):
    for j in range(0, df.shape[0]):
        m1 = Chem.MolFromSmiles(df.iloc[i, 1])
        fp1 = AllChem.GetMorganFingerprint(m1,2)
        m2 = Chem.MolFromSmiles(df.iloc[j, 1])
        fp2 = AllChem.GetMorganFingerprint(m2,2)
        sim = DataStructs.DiceSimilarity(fp1,fp2)
        if sim >= 0.99:
            s1.append(i)
            s2.append(j)
for k in range(0, len(s1)):
    if df.iloc[s1[k], 0] != df.iloc[s2[k], 0]:
        d1.append(df.iloc[s1[k], 0])
        d2.append(df.iloc[s2[k], 0])
if len(d1) != 0:
    with open('outputfile.tsv', 'a') as f2:
        for o in range(0, len(d1)):
            f2.write(str(d1[o]) + '\t' + str(d2[0]) + '\n')
4

1 回答 1

2

我不知道算法应该做什么，因此我不打算对此发表评论。但是，你说的是：

经过一番研究，我明白它必须是 O(n)！

代表什么n？如果算法的时间复杂度与数据集中的行数成线性关系，那么您的实现一定是不正确的。您的代码中有两个嵌套循环，两个循环的长度都n意味着您的算法O(n^2)处于最佳状态（不考虑循环内的其他函数在做什么）。

以下是一些如何在一定程度上加快代码速度的建议（通常在使用 pandas 时）。

您应该避免自己进行迭代，并且应该避免将 pandas 数据结构转换为 python 列表。这是一个例子：

for i in range(0, df.shape[0]):
        l.append(df.iloc[i, 1])

如果您确实需要将其存储在另一个变量中，那么您可以使用

l = df.iloc[:, 1].copy()

这会更快，并且不会将该系列变成一个列表（但我看不到l在您的代码中的任何地方使用，因此您可能应该完全放弃它）。

另一个例子是当您在嵌套循环内计算这些函数时（同样，我不知道它们在做什么，但这并不重要）。

for i ...
    for j ...
        m1 = Chem.MolFromSmiles(df.iloc[i, 1])
        fp1 = AllChem.GetMorganFingerprint(m1,2) 
        m2 = Chem.MolFromSmiles(df.iloc[j, 1])
        fp2 = AllChem.GetMorganFingerprint(m2,2)

首先，您要计算两次相同的值，这可能很耗时，而且您是在自定义循环中进行的，这也不是最好的主意。

您可以创建一个新的值列，而不是这 4 行（包括循环语句在内的 6 行）fp：

df["fp"] = df.iloc[:, i].copy()
df["fp"].apply(lambda x: AllChem.GetMorganFingerprint(Chem.MolFromSmiles(x), 2))

这样，您不必计算两次值，也不必编写自己的循环（至少对于这一部分）。

此时，您将需要弄清楚上述O(n)算法是如何工作的，但我想它可以转换为纯向量运算，这可能是最有效的实现。

于 2020-02-15T10:49:02.550 回答