CS50 'DNA'：加快第 6 周 'dna.py' 计划的方法？

Question

因此，对于这个问题，我不得不创建一个接受两个参数的程序。像这样的 CSV 数据库：

name,AGATC,AATG,TATC
Alice,2,8,3
Bob,4,1,5
Charlie,3,2,5

像这样的 DNA 序列：

TAAAAGGTGAGTTAAATAGAATAGGTTAAAATTAAAGGAGATCAGATCAGATCAGATCTATCTATCTATCTATCTATCAGAAAAGAGTAAATAGTTAAAGAGTAAGATATTGAATTAATGGAAAATATTGTTGGGGAAAGGAGGGATAGAAGG

我的程序首先从数据库（AGATC 等）中获取“短串联重复序列”(STR) headers，然后计算序列中每个 STR 连续重复的最高次数。最后，它将这些计数值与数据库中每一行的值进行比较，如果找到匹配则打印出名称，否则打印出“不匹配”。

该程序确实可以运行，但是每当运行使用所提供的更大的数据库时，它就会慢得离谱，以至于终端会在 return 输出任何内容之前暂停整整一分钟。不幸的是，这导致 'check50' 标记系统在使用这个大型数据库进行测试时 time-out 和 return 为负结果。

我假设速度下降是由 'STR_count' 函数中的嵌套循环引起的：

def STR_count(sequence, seq_len, STR_array, STR_array_len):
    # Creates a list to store max recurrence values for each STR
    STR_count_values = [0] * STR_array_len
    # Temp value to store current count of STR recurrence
    temp_value = 0

    # Iterates over each STR in STR_array
    for i in range(STR_array_len):
        STR_len = len(STR_array[i])

        # Iterates over each sequence element
        for j in range(seq_len):
            # Ensures it's still physically possible for STR to be present in sequence
            while (seq_len - j >= STR_len):
                # Gets sequence substring of length STR_len, starting from jth element
                sub = sequence[j:(j + (STR_len))]

                # Compares current substring to current STR
                if (sub == STR_array[i]):
                    temp_value += 1
                    j += STR_len
                else:
                    # Ensures current STR_count_value is highest
                    if (temp_value > STR_count_values[i]):
                        STR_count_values[i] = temp_value
                    # Resets temp_value to break count, and pushes j forward by 1
                    temp_value = 0
                    j += 1
        i += 1

    return STR_count_values

和 'DNA_match' 函数：

# Searches database file for DNA matches
def DNA_match(STR_values, arg_database, STR_array_len):
    with open(arg_database, 'r') as csv_database:
        database = csv.reader(csv_database)

        name_array = [] * (STR_array_len + 1)
        next(database)

        # Iterates over one row of database at a time
        for row in database:
            name_array.clear()
            # Copies entire row into name_array list
            for column in row:
                name_array.append(column)

            # Converts name_array number strings to actual ints
            for i in range(STR_array_len):
                name_array[i + 1] = int(name_array[i + 1])

            # Checks if a row's STR values match the sequence's values, prints the row name if match is found
            match = 0
            for i in range(0, STR_array_len, + 1):
                if (name_array[i + 1] == STR_values[i]):
                    match += 1

                if (match == STR_array_len):
                    print(name_array[0])
                    exit()

        print("No match")
        exit()

但是，我是 Python 的新手，之前没有真正考虑过速度，所以我不确定如何改进它。

我并不是特别想找人为我做我的工作，所以我很高兴任何建议尽可能模糊。老实说，我会重视任何反馈，包括风格建议，因为我只能想象这段代码对于那些更有经验的人来说是多么令人厌恶。

Here's a link to the full program，如果有帮助。

谢谢 :) x

Answer 1

感谢您为整个程序提供 link。它似乎不必要地复杂，但我想说它只是缺乏对您可用的功能的了解。我认为您已经确定了导致速度缓慢的代码部分 - 我还没有分析它或其他任何东西，但我的第一个冲动也是 STR_count.

中的三个嵌套循环

以下是我的编写方式，利用了 Python 标准库。数据库中的每个条目都对应一个 person，所以这就是我对它们的称呼。 people 是一个字典列表，其中每个字典代表数据库中的一行。我们使用 csv.DictReader.

免费获得这个

为了找到序列中的匹配项，对于数据库中的每个短串联重复序列，我们创建一个正则表达式模式（当前的短串联重复序列，重复一次或多次）。如果序列中存在匹配，则重复的总数等于匹配的长度除以当前串联重复的长度。例如，如果 AGATCAGATCAGATC 存在于序列中，并且当前串联重复为 AGATC，则重复次数将为 len("AGATCAGATCAGATC") // len("AGATC") 即 15 // 5，即 3.

count 只是一个字典，将短串联重复序列映射到序列中相应的重复次数。最后，我们搜索短串联重复计数与 count 完全匹配的人，并打印他们的名字。如果不存在这样的人，我们打印 "No match".

def main():

    import argparse
    from csv import DictReader
    import re

    parser = argparse.ArgumentParser()
    parser.add_argument("database_filename")
    parser.add_argument("sequence_filename")

    args = parser.parse_args()

    with open(args.database_filename, "r") as file:
        reader = DictReader(file)
        short_tandem_repeats = reader.fieldnames[1:]
        people = list(reader)

    with open(args.sequence_filename, "r") as file:
        sequence = file.read().strip()

    count = dict(zip(short_tandem_repeats, [0] * len(short_tandem_repeats)))

    for short_tandem_repeat in short_tandem_repeats:
        pattern = f"({short_tandem_repeat}){{1,}}"
        match = re.search(pattern, sequence)
        if match is None:
            continue
        count[short_tandem_repeat] = len(match.group()) // len(short_tandem_repeat)

    try:
        person = next(person for person in people if all(int(person[k]) == count[k] for k in short_tandem_repeats))
        print(person["name"])
    except StopIteration:
        print("No match")
    
    return 0


if __name__ == "__main__":
    import sys
    sys.exit(main())

CS50 'DNA'：加快第 6 周 'dna.py' 计划的方法？

CS50 'DNA': Ways to speed up my Week 6 'dna.py' program?

python

cs50