Как найти элементы большого массива (1 миллион элементов) в другом массиве большего размера (600 миллионов элементов)

Question

У меня есть очень большой файл (содержащий dbSNP ID), содержащий 1 миллион строк, каждая из которых содержит одну строку, и еще один большой файл (.vcf), содержащий 600 миллионов строк, каждая из которых содержит 7-8 столбцов.

Я хочу найти первое вхождение каждой строки меньшего файла в больший файл, чтобы сложность моей программы была грубой силой в 1 000 000 * 600 000 000 раз. Я хочу более быстрый и менее интенсивный способ памяти. Я новичок в многопроцессорном или параллельном программировании на python, и я не уверен, как решить эту проблему, не используя ни того, ни другого.

Я пытался сделать что-то подобное для меньшего подмножества обоих файлов, используя библиотеки numpy и pandas:

import numpy as np
import pandas as pd

BigFile = pd.Series(arrayOfRowsOfBiggerFile)
SmallFile = pd.Series(arrayOfRowsOfSmallerFile)
FinalList = SmallFile.map(lambda x: np.where(A==x)[0][0]).tolist()

Это выполняется вечно, и я уверен, что с многопроцессорной обработкой в ​​Python можно справиться хорошо.

Answer 1

Если я правильно понял, вы фактически выполняете операцию join: вам нужны все строки в VCF, ключ которых (в данном случае RSID) появляется в вашем "меньшем" файле. Смотрите документы здесь: https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.join.html

И ваш код будет выглядеть примерно так:

dbsnp = pd.read_csv('path/to/dbsnp', index_col='rsid', ...)
rsids_of_interest = pd.read_csv('path/to/smaller_file', ...)

subset_of_dbsnp = dbsnp.join(rsids_of_interest, how='inner', ...)

Answer 2

Если вы хотите просто извлечь подмножество файла .vcf на основе списка вариантов, вы можете

( 1 ) использовать решение, предложенное @OronNavon.Это должно работать по крайней мере с небольшими файлами.При больших размерах файлов это может потребовать большого количества вычислительных ресурсов, что не обязательно является проблемой, если у вас есть доступ к кластеру.Если вы используете его на домашнем ПК, вам может не хватить памяти.Вы можете обойти это, читая файл на лету, но это все еще медленный процесс.Кроме того, вы, вероятно, потеряете заголовок .vcf со всеми метаданными, поэтому, если вам это нужно (или .vcf), вы должны добавить его отдельно.

( 2 ) разбить файл .vcf на куски, которые вы можете запускать параллельно, если хотите.Хотя это будет не так эффективно, как могло бы быть, поскольку у вас есть только rsID, а не места в вашем меньшем файле.

( 3 ) используйте Plink , который представляет собой автономный пакет, но он может выполнять работу быстро / эффективно.(Это то, что я бы сделал.)