algorithm - python : Can I grab the specific lines from a large file faster?

Question

我有两个大文件。其中之一是一个信息文件(大约 270MB 和 16,000,000 行)，如下所示:

1101:10003:17729
1101:10003:19979
1101:10003:23319
1101:10003:24972
1101:10003:2539
1101:10003:28242
1101:10003:28804

另一种是标准的FASTQ格式(大约27G和280,000,000行)，像这样:

@ST-E00126:65:H3VJ2CCXX:7:1101:1416:1801 1:N:0:5
NTGCCTGACCGTACCGAGGCTAACCCTAATGAGCTTAATCAAGATGATGCTCGTTATGG
+
AAAFFKKKKKKKKKFKKKKKKKFKKKKAFKKKKKAF7AAFFKFAAFFFKKF7FF<FKK
@ST-E00126:65:H3VJ2CCXX:7:1101:10003:75641:N:0:5
TAAGATAGATAGCCGAGGCTAACCCTAATGAGCTTAATCAAGATGATGCTCGTTATGG
+
AAAFFKKKKKKKKKFKKKKKKKFKKKKAFKKKKKAF7AAFFKFAAFFFKKF7FF<FKK

FASTQ 文件每个序列使用四行。第 1 行以“@”字符开头，后跟序列标识符。对于每个序列，第 1 行的这部分是唯一的。

1101:1416:1801 and 1101:10003:75641

我想根据信息文件从FASTQ文件中抓取第1行和接下来的三行。这是我的代码:

import gzip
import re

count = 0
with open('info_path') as info, open('grab_path','w') as grab:
        for i in info:
                sample = i.strip()
                with gzip.open('fq_path') as fq:
                        for j in fq:
                                count += 1
                                if count%4 == 1:
                                        line = j.strip()
                                        m = re.search(sample,j)
                                        if m != None:
                                                grab.writelines(line+'\n'+fq.next()+fq.next()+fq.next())
                                                count = 0
                                                break

它确实有效，但是因为这两个文件都有数百万行，所以效率很低(运行一天只能得到 20,000 行)。

7 月 6 日更新:

我发现info文件可以读入内存(感谢@tobias_k提醒)，所以我创建了一个字典，key是info lines，values都是0，然后读取FASTQ文件每 4 行，使用标识符部分作为键，如果值为 0，则返回这 4 行。这是我的代码:

import gzip

dic = {}
with open('info_path') as info:
        for i in info:
                sample = i.strip()
                dic[sample] = 0
with gzip.open('fq_path') as fq, open('grap_path',"w") as grab:
        for j in fq:
                if j[:10] == '@ST-E00126':
                        line = j.split(':')
                        match = line[4] +':'+line[5]+':'+line[6][:-2]
                        if dic.get(match) == 0:
                                grab.writelines(j+fq.next()+fq.next()+fq.next())

这种方式要快得多，需要20分钟才能得到所有匹配的行(大约64,000,000行)。而且我考虑过首先通过外部排序对FASTQ文件进行排序。把能读取的文件拆分到内存就可以了，我的麻烦是排序的时候怎么让接下来的三行跟在标识符行后面。谷歌的回答是先把这四行线性化，但是需要40分钟。

无论如何感谢您的帮助。

Answer 1

您可以按标识符(1101:1416:1801)部分对这两个文件进行排序。即使文件不适合内存，您也可以使用 external sorting .

在此之后，您可以应用一个简单的类似合并的策略:一起读取两个文件并同时进行匹配。像这样的东西(伪代码):

entry1 = readFromFile1()
entry2 = readFromFile2()
while (none of the files ended)
    if (entry1.id == entry2.id)
        record match
    else if (entry1.id < entry2.id)
        entry1 = readFromFile1()
    else 
        entry2 = readFromFile2()

这样 entry1.id 和 entry2.id 总是彼此接近，你不会错过任何匹配。同时，这种方法需要对每个文件进行一次迭代。