Python - Проверка согласованности между двумя огромными текстовыми файлами

Question

Итак, это дало мне тяжелое время!
Я работаю с HUGE текстовыми файлами, и огромным я имею в виду 100Gb +. В частности, они находятся в fastq format. Этот формат используется для данных секвенирования ДНК, и состоит из записей четырех линий, что-то вроде этого:

@REC1 
GATTTGGGGTTCAAAGCAGTATCGATCAAATAGTAAATCCATTTGTTCAACTCACAGTTT 
+ 
!''*((((***+))%%%++)(%%%%).1***-+*''))*55CCF>>>>>>CCCCCCC65 
@REC2 
GATTTGGGGTTCAAAGCAGTATCGATCAAATAGTAAATCCATTTGTTCAACTCACAGTTT 
+ 
!''*((((***+))%%%++)(%%%%).1***-+*''))**55CCF>>>>>>CCCCCCC65 
. 
. 
. 

Ради этого вопроса, просто сосредоточиться на строках заголовков, начиная с «@».

Итак, для целей QA мне нужно сравнить два таких файла. Эти файлы должны иметь соответствующие заголовки, поэтому первая запись в другом файле также должна иметь заголовок '@ REC1', следующий должен быть '@ REC2' и так далее. Я хочу убедиться, что это так, прежде чем я начну анализировать тяжелые анализы.
Поскольку файлы настолько велики, наивная итерация сравнения строк займет очень много времени, но этот шаг QA будет выполняться много раз, и я не могу позволить себе так долго ждать. Поэтому я подумал, что лучший способ - собрать образцы из нескольких точек в файлах, например, каждые 10% записей. Если порядок записей будет испорчен, я бы с большой вероятностью его обнаружил.
До сих пор я мог обрабатывать такие файлы, оценивая размер файла и используя file.seek() python для доступа к записи в середине файла. Например, чтобы получить доступ к линии примерно в середине, я бы:

file_size = os.stat(fastq_file).st_size 
start_point = int(file_size/2) 
with open(fastq_file) as f: 
    f.seek(start_point) 
    # look for the next beginning of record, never mind how 

Но теперь эта проблема является более сложной, так как я не знаю, как координировать между двумя файлами, так как местоположение байтов не является индикатором индекса строки в файле. Другими словами, как я могу получить доступ к 10 567 311 строкам в обоих файлах, чтобы убедиться, что они одинаковые, не обойдя весь файл?

Поблагодарили бы за любые идеи \ hints. Может быть, итерация параллельно? но как именно?
Спасибо!

Answer 1

Отбор проб - это один подход, но вы полагаетесь на удачу. Кроме того, Python является неправильным инструментом для этой работы. Вы можете сделать что-то по-другому, и вычислить точный ответ на все еще достаточно эффективном способе, используя стандартные средства Unix командной строки:

1. линеаризует ваш FASTQ запись: заменить символ новой строки в первых трех строках с закладками.
2. Запустить diff на пару линеаризованных файлов. Если есть разница, diff сообщит об этом.

линеаризацию, вы можете запустить файл FASTQ через awk:

$ awk '\ 
    BEGIN { \ 
     n = 0; \ 
    } \ 
    { \ 
     a[n % 4] = $0; \ 
     if ((n+1) % 4 == 0) { \ 
     print a[0]"\t"a[1]"\t"a[2]"\t"a[3]; \ 
     } \ 
     n++; \ 
    }' example.fq > example.fq.linear 

Для сравнения пару файлов:

$ diff example_1.fq.linear example_2.fq.linear 

Если есть какая-то разница, diff будет найти его и сказать вы, какая запись FASTQ отличается.

Вы можете просто запустить diff по двум файлам напрямую, не выполняя дополнительную работу по линеаризации, но легче видеть, что чтение проблематично, если вы сначала линеаризуете.

Так что это большие файлы. Написание новых файлов является дорогостоящим во времени и на диске.Есть способ улучшить это, используя streams.

Если поместить awk скрипт в файл (например, , linearize_fq.awk), вы можете запустить его следующим образом:

$ awk -f linearize_fq.awk example.fq > example.fq.linear 

Это может быть полезно с 100+ файлов Gb, в том, что вы можете Теперь создать два потока файлов Unix через bashprocess substitutions и запустить diff на эти потоки непосредственно:

$ diff <(awk -f linearize_fq.awk example_1.fq) <(awk -f linearize_fq.awk example_2.fq) 

Или вы можете использовать named pipes:

$ mkfifo example_1.fq.linear 
$ mkfifo example_2.fq.linear 
$ awk -f linearize_fq.awk example_1.fq > example_1.fq.linear & 
$ awk -f linearize_fq.awk example_2.fq > example_2.fq.linear & 
$ diff example_1.fq.linear example_2.fq.linear 
$ rm example_1.fq.linear example_2.fq.linear 

Оба именованных канала и подстановки процесса не позволяют создать дополнительные (обычные) файлы, что может быть проблемой для вашего типа ввода. Написание линеаризованных копий более 100 Gb-файлов на диск может занять некоторое время, и эти копии могут также использовать дисковое пространство, в котором вы, возможно, не много.

Использование потоков позволяет обойти эти две проблемы, что делает их очень полезными для эффективного использования наборов данных биоинформатики.

Вы можете воспроизвести эти подходы с помощью Python, но он почти наверняка будет работать намного медленнее, так как Python очень медленный в таких тяжелых задачах ввода-вывода.

Answer 2

Итерация параллельно может быть лучшим способом сделать это в Python. Я не знаю, как быстро это будет работать (быстрый SSD, вероятно, будет лучшим способом ускорить это), но так как вам все равно придется подсчитывать символы новой строки в обоих файлах, я не вижу способа обойти это:

with open(file1) as f1, open(file2) as f2: 
    for l1, l2 in zip(f1,f2): 
     if l1.startswith("@REC"): 
      if l1 != l2: 
       print("Difference at record", l1) 
       break 
    else: 
     print("No differences") 

Это написано для Python 3, где zip возвращает итератор; в Python 2 вместо этого вы должны использовать itertools.izip().

Answer 3

import sys 
import re 

""" To find of the difference record in two HUGE files. This is expected to 
use of minimal memory. """ 

def get_rec_num(fd): 
    """ Look for the record number. If not found return -1""" 
    while True: 
     line = fd.readline() 
     if len(line) == 0: break 
     match = re.search('^@REC(\d+)', line) 
     if match: 
      num = int(match.group(1)) 
      return(num) 
    return(-1) 

f1 = open('hugefile1', 'r') 
f2 = open('hugefile2', 'r') 

hf1 = dict() 
hf2 = dict() 
while f1 or f2: 
    if f1: 
     r = get_rec_num(f1) 
     if r < 0: 
      f1.close() 
      f1 = None 
     else: 
      # if r is found in f2 hash, no need to store in f1 hash 
      if not r in hf2: 
       hf1[r] = 1 
      else: 
       del(hf2[r]) 
     pass 
    pass 
    if f2: 
     r = get_rec_num(f2) 
     if r < 0: 
      f2.close() 
      f2 = None 
     else: 
      # if r is found in f1 hash, no need to store in f2 hash 
      if not r in hf1: 
       hf2[r] = 1 
      else: 
       del(hf1[r]) 
     pass 
    pass 

print('Records found only in f1:') 
for r in hf1: 
    print('{}, '.format(r)); 
print('Records found only in f2:') 
for r in hf2: 
    print('{}, '.format(r)); 

Answer 4

Оба ответа от @AlexReynolds и @TimPietzcker отлично с моей точки зрения, но я хотел бы поставить свои два цента Вы также можете ускорить ваше оборудование:.

• Raplace HDD с SSD
• Сделайте n SSD и создайте RAID 0. В идеальном мире вы получите n раз быстрее для вашего диска IO.
• Отрегулируйте размер кусков, которые вы читаете с SSD/HDD. Я ожидал бы, например, один 16 МБ чтения для выполнения быстрее, чем 16 МБ чтения. (это относится к одному SSD, для оптимизации RAID 0 нужно взглянуть на опции и возможности RAID-контроллера).

Последний вариант особенно важен для SSD NOR. Не преследуйте минимальное использование ОЗУ, но старайтесь читать столько, сколько нужно, чтобы ваш диск быстро читал. Например, параллельные чтения отдельных строк из двух файлов могут, вероятно, ускорить чтение - представьте себе жесткий диск, где две строки из двух файлов всегда находятся на одной стороне одного и того же магнитного диска (дисков).

Answer 5

Вы изучили использование команды rdiff.
В расквитаться из RDIFF являются:

• с теми же файлами 4,5 Гб, RDIFF ели только около 66MB оперативной памяти и масштабируется очень хорошо. Он никогда не разбивался на сегодняшний день.
• это также МНОГО быстрее, чем различие.
• RDIFF себе сочетает Diff и коммутационные возможности, так что вы можете создать дельты и применять их, используя ту же самую программу

Недостатков RDIFF являются:

• это не входит в стандартном Linux/UNIX распространение - вы должны установить пакет librsync.
• Файлы дельта rdiff имеют немного отличающийся формат, чем diff.
• Дельта-файлы немного больше (но недостаточно для ухода).
• При генерации дельта с rdiff, который является хорошим и плохим, используется несколько иной подход - требуется 2 шага. Сначала создает специальный файл подписи. На втором этапе создается дельта с использованием другого вызова rdiff (все это показано ниже). В то время как двухэтапный процесс может показаться раздражающим, он имеет преимущества , обеспечивающие более быструю дельта, чем при использовании diff.

См: http://beerpla.net/2008/05/12/a-better-diff-or-what-to-do-when-gnu-diff-runs-out-of-memory-diff-memory-exhausted/