ГИБКОЕ УДЛИНЕНИЕ ЗАТРАВКИ ДЛЯ ГЕНОМНОГО КАРТИРОВАНИЯ НА ОСНОВЕ ХЕШ-ТАБЛИЦЫ Российский патент 2023 года по МПК G06F16/2455 G06F16/22 

ПЕРЕКРЕСТНАЯ ССЫЛКА НА РОДСТВЕННУЮ ЗАЯВКУ

[0001] Данная заявка испрашивает преимущество по предварительной заявке на патент США № 62/852,965, поданной 24 мая 2019 г., которая полностью включена в настоящий документ путем ссылки.

ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ

[0002] Секвенатор нуклеиновых кислот представляет собой инструмент, выполненный с возможностью автоматизации процесса секвенирования нуклеиновых кислот. Секвенирование нуклеиновых кислот представляет собой процесс определения порядка нуклеотидов в нуклеотидной последовательности. К нуклеиновым кислотам могут относиться дезоксирибонуклеиновая кислота (ДНК) или рибонуклеиновая кислота (РНК).

[0003] Секвенатор нуклеиновых кислот выполнен с возможностью приема образца нуклеиновой кислоты и генерирования выходных данных, называемых одним или более «чтениями», которые отражают порядок нуклеотидов в образце нуклеиновой кислоты. Нуклеотиды в образце ДНК могут включать одно или более нуклеотидных оснований, включающих гуанин (G), цитозин (C), аденин (A) и тимин (T) в любой комбинации. Нуклеотиды в образце РНК могут включать одно или более оснований, включающих G, C, A и урацил (U) в любой комбинации.

[0004] Чтения, генерируемые секвенатором ДНК, могут быть сопоставлены (картированы) с известной последовательностью нуклеотидов эталонного генома с помощью модуля картирования и выравнивания. Картирование чтений с последовательностью нуклеотидов эталонного генома может быть выполнено системой картирования и выравнивания, в которой используют индекс хеш-таблицы.

ИЗЛОЖЕНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

[0005] В настоящем описании представлены составление и применение индекса хеш-таблицы, облегчающего гибкое удлинение затравки для повышения эффективности систем картирования и выравнивания генома. В частности, настоящее описание можно использовать для осуществления гибкого удлинения затравки с возможностью (i) снижения затрат вычислительных ресурсов и энергии и (ii) решения проблем традиционных способов удлинения затравки, описанных в настоящем документе. Для достижения этих преимуществ в настоящем описании обеспечена, среди прочего, «запись об интервале», которая может храниться в некоторой позиции хеш-таблицы.

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

[0007] В одном аспекте в настоящем описании предложены способы генерирования хеш-таблицы для картирования чтений образца по эталону. В одном аспекте способы могут включать получение с помощью компьютерной системы первой нуклеотидной затравки из эталонной последовательности, причем первая затравка имеет K нуклеотидов; определение с помощью компьютерной системы, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности; на основании определения того, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование с помощью компьютерной системы дерева удлинения затравки, имеющего множество узлов, причем каждый узел из множества узлов соответствует (i) удлиненной затравке, которая представляет собой удлинение первой затравки и имеет количество нуклеотидов K*, причем K* на один или более нуклеотидов больше, чем K, и (ii) одной или более позициям в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, а также для каждого узла из множества узлов: сохранение с помощью компьютерной системы информации об интервале в позиции хеш-таблицы, которая соответствует индексному ключу удлиненной затравки, причем информация об интервале ссылается на одну или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, ассоциированной с узлом.

[0008] Другие аспекты включают соответствующие системы, аппарат и компьютерные программы для выполнения операций из способов, описанных в настоящем документе, согласно определению в командах, закодированных на машиночитаемых устройствах хранения.

[0009] Эти и другие аспекты могут необязательно включать один или более из представленных ниже признаков. Например, в некоторых вариантах осуществления каждая из совпадающих позиций эталонной последовательности включает в себя K нуклеотидов первой затравки.

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

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

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

[0013] В некоторых вариантах осуществления получение с помощью компьютерной системы первой нуклеотидной затравки из эталонной последовательности, причем первая затравка представляет собой нуклеотидную последовательность с K нуклеотидов, может включать определение с помощью компьютерной системы позиции окна доступа к затравке в пределах эталонной последовательности и получение с помощью компьютерной системы части эталонной последовательности, идентифицированной окном доступа к затравке.

[0014] В некоторых вариантах осуществления способы могут дополнительно включать смещение с помощью компьютерной системы окна удлинений затравки на K нуклеотидов вперед вдоль эталонной последовательности для идентификации на эталонной последовательности второй нуклеотидной затравки, имеющей K нуклеотидов, получение с помощью компьютерной системы второй затравки из эталонной последовательности; определение с помощью компьютерной системы, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности; на основании определения того, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование с помощью компьютерной системы второго дерева удлинения затравки, имеющего множество вторых узлов, причем каждый из вторых узлов множества вторых узлов соответствует (i) второй удлиненной затравке, которая представляет собой удлинение второй затравки и имеет количество нуклеотидов K*, причем K* на один или более нуклеотидов больше, чем K, и (ii) одной или более вторым позициям во второй таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают со второй удлиненной затравкой; и для каждого второго узла из множества вторых узлов: сохранение с помощью компьютерной системы второй информации об интервале в позиции хеш-таблицы, которая соответствует индексному ключу второй удлиненной затравки, причем вторая информация об интервале ссылается на одну или более позиций во второй таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают со второй удлиненной затравкой, ассоциированной со вторым узлом.

[0015] В некоторых вариантах осуществления способы могут дополнительно включать для каждого узла из множества узлов: определение с помощью компьютерной системы, является ли узел дерева удлинения затравки концевым узлом, и сохранение с помощью компьютерной системы записи об удлинении в позиции хеш-таблицы, которая соответствует индексному ключу удлиненной затравки, на основании определения с помощью компьютерной системы, что узел дерева удлинений не является концевым узлом.

[0016] В некоторых вариантах осуществления запись об удлинении включает в себя одну или более команд, за счет исполнения которых компьютерная система добавляет один или более дополнительных нуклеотидов к затравке, ассоциированной с записью об удлинении.

[0017] В некоторых вариантах осуществления способы могут дополнительно включать на основании определения с помощью компьютерной системы, что узел дерева удлинений представляет собой концевой узел, принятие компьютерной системой решения не сохранять запись об удлинении в позиции хеш-таблицы, которая соответствует индексному ключу для удлиненной затравки.

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

[0019] В некоторых вариантах осуществления способы могут дополнительно включать сортировку с помощью компьютерной системы выявленных затравок в таблице удлинений затравки.

[0020] В некоторых вариантах осуществления способы могут дополнительно включать генерирование с помощью компьютерной системы пакета для инсталляции хеш-таблицы, причем пакет для инсталляции хеш-таблицы включает в себя команды, при обработке которых одним или более компьютерами, принявшими пакет для инсталляции хеш-таблицы, один или более компьютеров устанавливают хеш-таблицу в память, доступную для программируемой логической схемы.

[0021] В некоторых вариантах осуществления пакет для инсталляции хеш-таблицы может включать в себя таблицу удлинений затравки, а пакет для инсталляции хеш-таблицы может включать в себя команды для сохранения (i) программируемой логической схемой или (ii) другим компьютером таблицы удлинений затравки в запоминающем устройстве, доступном для программируемой логической схемы.

[0022] В некоторых вариантах осуществления предоставление пакета для инсталляции хеш-таблицы другому компьютеру компьютерной системой.

[0023] В некоторых вариантах осуществления другой компьютер может включать в себя (i) компьютер, выполненный с возможностью обмена данными с программируемой логической схемой, или (ii) саму программируемую логическую схему.

[0024] В некоторых вариантах осуществления компьютерная система может включать в себя множество компьютеров.

[0025] В другом аспекте в настоящем описании предложены способы применения хеш-таблицы для улучшения картирования чтений образцов с эталонной последовательностью. В одном аспекте способы могут включать выполнение запроса к хеш-таблице блоком картирования и выравнивания, причем запрос включает в себя первую затравку, при этом первая затравка включает в себя подгруппу нуклеотидов, которые были получены из конкретного чтения из числа чтений образца, получение блоком картирования и выравнивания ответа на выполненный запрос, включая информацию, хранящуюся в позиции хеш-таблицы, определяемую как ответ на запрос, определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности, на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены (i) запись об удлинении и (ii) запись об интервале: определение блоком картирования и выравнивания, должен ли быть доступ к таблице удлинений для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается запись об интервале, а на основании определения, что доступ к таблице удлинений не нужен: определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал, генерирование блоком картирования и выравнивания первой удлиненной затравки, которая представляет собой удлинение первой затравки с использованием записи об удлинении, генерирование блоком картирования и выравнивания последующего хеш-запроса, который включает в себя первую удлиненную затравку, и выполнение блоком картирования и выравнивания последующего хеш-запроса к хеш-таблице.

[0026] Другие версии включают соответствующие системы, аппарат и компьютерные программы для выполнения действий из способов, определяемых командами, закодированными на машиночитаемых устройствах хранения.

[0027] Эти и другие аспекты описания могут необязательно включать один или более из представленных ниже признаков. Например, в некоторых вариантах осуществления способы могут дополнительно включать на основании определения, что доступ к таблице удлинений нужен: получение блоком картирования и выравнивания доступа к таблице удлинений и получение одной или более позиций в таблице удлинений, на которые ссылается запись об интервале, совпадающих эталонной последовательности, и добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

[0028] В некоторых вариантах осуществления способы могут дополнительно включать определение блоком картирования и выравнивания, что в ответ на выполненный запрос включены одна или более совпадающих позиций эталонной последовательности, и на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены одна или более совпадающих позиций эталонной последовательности: добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

[0029] В некоторых вариантах осуществления определение блоком картирования и выравнивания, хранить ли первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал, может включать определение блоком картирования и выравнивания отсутствия предыдущей информации, описывающей запись об интервале в качестве потенциального наилучшего интервала для конкретного чтения, и сохранение блоком картирования и выравнивания первой информации, описывающей запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал.

[0030] В некоторых вариантах осуществления способы могут дополнительно включать получение блоком картирования и выравнивания ответа на последующий выполненный запрос, включая информацию, хранящуюся в позиции хеш-таблицы, определяемой как ответ на запрос, определение блоком картирования и выравнивания, включены ли в ответ на последующий выполненный запрос (i) вторая запись об удлинении, (ii) вторая запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности, на основании определения блоком картирования и выравнивания, что в ответ на последующий выполненный запрос включены (i) вторая запись об удлинении или (ii) вторая запись об интервале: определение блоком картирования и выравнивания, должен ли быть доступ к таблице удлинений для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается вторая запись об интервале, на основании определения, что доступ к таблице удлинений не нужен: определение блоком картирования и выравнивания и с помощью одного или более эвристических правил, следует ли использовать вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала, генерирование блоком картирования и выравнивания второй удлиненной затравки, которая представляет собой удлинение первой удлиненной затравки с использованием второй записи об удлинении, генерирование блоком картирования и выравнивания третьего хеш-запроса, который включает в себя вторую удлиненную затравку; и выполнение блоком картирования и выравнивания третьего запроса к хеш-таблице, который включает в себя вторую удлиненную затравку.

[0031] В некоторых вариантах осуществления определение блоком картирования и выравнивания с использованием одного или более эвристических правил, нужно ли использовать вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве наилучшего интервала может включать выбор либо второй информации, описывающей вторую запись об интервале, либо первой информации, описывающей запись о потенциальном наилучшем интервале, на основании множества факторов, которые включают в себя (i) количество совпадающих позиций эталонной последовательности, полученное от каждой из записи об интервале и второй записи об интервале, (ii) заданное пороговое количество позиций эталонной последовательности или (iii) длину каждой из соответствующих затравок, достигших хеш-позиций, в которых хранятся запись об интервале и вторая запись об интервале.

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

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

[0034] Если не указано иное, все технические и научные термины, используемые в настоящем документе, имеют общепринятое значение, понятное любому обычному специалисту в данной области, к которой относится настоящее изобретение. В настоящем документе описаны примеры способов и материалов, хотя для проверки или анализа настоящего изобретения можно использовать подходящие способы и материалы, подобные или эквивалентные описанным ниже. Все публикации, заявки на патенты, патенты и другие упоминаемые в настоящем документе литературные источники включены в настоящий документ в полном объеме путем ссылки. В случае противоречий настоящее описание, включая определения, будет иметь приоритет. Кроме того, материалы, способы и примеры приведены только для иллюстрации и не имеют ограничительного характера.

[0035] Эти и другие аспекты настоящего описания более подробно описаны ниже со ссылкой на прилагаемые чертежи и пункты формулы изобретения.

КРАТКОЕ ОПИСАНИЕ ГРАФИЧЕСКИХ МАТЕРИАЛОВ

[0036] На ФИГ. 1 представлена контекстная схема системы для генерирования индекса хеш-таблицы, облегчающей гибкое удлинение затравки для геномного картирования на основе хеш-таблицы.

[0037] На ФИГ. 2 представлена блок-схема процесса генерирования индекса хеш-таблицы, облегчающего гибкое удлинение затравки для геномного картирования на основе хеш-таблицы.

[0038] На ФИГ. 3 представлена контекстная схема исполнительной системы для оперативного выполнения гибкого удлинения затравки для геномного картирования на основе хеш-таблицы.

[0039] На ФИГ. 4 представлена блок-схема процесса выполнения оперативного гибкого удлинения затравки для геномного картирования на основе хеш-таблицы.

[0040] На ФИГ. 5 представлена блок-схема процесса выполнения итеративного оперативного гибкого удлинения затравки для геномного картирования на основе хеш-таблицы на каждой затравке чтения.

[0041] На ФИГ. 6 представлена схема компонентов системы, которые можно использовать для реализации описанных в настоящем документе систем, относящихся к гибким удлинениям затравок, при геномном картировании на основе хеш-таблицы.

[0042] На ФИГ. 7 представлена гистограмма, отображающая данные результатов тестирования в виде процентной доли некартированных чтений в системе, в которой используют способ гибкого удлинения затравки, описанный в настоящем документе, по сравнению с системой, в которой не используют способ гибкого удлинения затравки.

[0043] На ФИГ. 8 представлен линейный график, отображающий данные результатов тестирования в виде точности картирования чтений в системе, в которой используют способ гибкого удлинения затравки, описанный в настоящем документе, по сравнению с системой, в которой не используют способ гибкого удлинения затравки.

ПОДРОБНОЕ ОПИСАНИЕ

[0044] В настоящем описании представлены составление и применение индекса хеш-таблицы, облегчающего гибкое удлинение затравки для повышения эффективности систем картирования и выравнивания генома. В настоящем документе термин «затравка» относится к подгруппе последовательных нуклеотидов, которые присутствуют в прочитанной нуклеиновой кислоте («чтении») или в эталонной нуклеотидной последовательности («эталонной последовательности»). Например, короткие затравки для чтения могут иметь, например, 21 основание или нуклеотид, которые извлечены из чтения, например 150 оснований или нуклеотидов, полученных секвенатором нуклеиновых кислот («секвенатором») на основе введенного в секвенатор биологического образца. Такие короткие затравки могут совпадать с сотнями, тысячами, сотнями тысяч или даже большим количеством позиций эталонной последовательности. Затравки для эталонной последовательности могут включать подгруппу последовательных нуклеотидов эталонной последовательности, отражающую позицию эталонной последовательности. Выявление в эталонных последовательностях таких больших количеств совпадающих позиций с конкретной короткой затравкой чтения, возможно по множеству причин, включая появление повторяющихся последовательностей, таких как «...ATATAT...», которые могут встречаться во многих позициях эталонной последовательности. В альтернативном или дополнительном варианте осуществления такое большое количество совпадающих эталонной последовательности позиций может возникать из-за того, что в эталонной последовательности может встречаться множество «почти копий» геномной последовательности.

[0045] При таком большом количестве позиций эталонной последовательности, совпадающих с конкретным коротким чтением, могут возникать затруднения в традиционных блоках картирования и выравнивания, использующих традиционные индексы хеш-таблиц, так как системы картирования и выравнивания могут быть вынуждены обрабатывать большое количество совпадений. Из-за такой чрезмерной обработки большого количества позиций эталонной последовательности, соответствующих конкретному короткому чтению, тратится больше вычислительных ресурсов, включая исчерпание процессорных ресурсов, ресурсов памяти, и тратится энергия, используемая для питания процессорных ресурсов, запоминающих устройств и блоков охлаждения, применяемых для охлаждения процессорных ресурсов и ресурсов памяти, или любой их комбинации.

[0046] Для решения проблем, которые могут возникать при идентификации и обработке большого числа позиций эталонной последовательности, совпадающих с короткой затравкой, применяют традиционные способы. Например, применяют традиционные способы, в которых для итеративного удлинения коротких затравок применяют записи об удлинениях, хранящиеся в позициях хеш-таблицы. К таким способам относятся, например, описанные в патенте США № 10,083,276, включенном в настоящий документ путем ссылки, и которые могут, например, возвращать «запись об удлинении», хранящуюся в позиции хеш-таблицы, соответствующей затравке хеш-запроса. Запись об удлинении можно использовать для создания удлиненной затравки путем симметричного увеличения длины затравки в принятом хеш-запросе путем добавления одного или более оснований или нуклеотидов на каждом конце затравки. Затем в традиционных системах может быть использован другой хеш-запрос, который включает в себя удлиненную затравку для повторного запроса к хеш-таблице. Этот другой хеш-запрос, содержащий удлиненную затравку, вероятно, будет соответствовать хеш-позиции, определяющей меньшее количество позиций эталонной последовательности, которые совпадают с удлиненной затравкой, поскольку удлиненная затравка длиннее. Такой итерационный процесс может продолжаться до (i) достаточного сокращения итогового набора совпадений, чтобы получилось количество совпадений удлиненной затравки с позициями эталонной последовательности меньше некоторого порогового количества, (ii) опустения набора совпадений, (iii) достижения максимального удлинения затравки или (iv) определения невозможности следующего удлинения из-за выхода за границу чтения, на котором основана короткая затравка. Очень важно, что в традиционной системе блок картирования и выравнивания способен получать непустой набор совпадающих с эталоном позиций только в том случае, если итерационный процесс завершается описанным выше способом (i), но не в том случае, если он завершается любым из вышеописанных способов (ii), (iii) или (iv).

[0047] Такими традиционными способами можно уменьшать количество позиций эталонной последовательности, которые совпадают с короткими затравками. Однако с этими традиционными способами связаны три отдельные проблемы.

[0048] Во-первых, традиционные способы могут быть подвержены «проблеме некартированных чтений». Проблема некартированных чтений возникает, когда с помощью традиционных способов удлинения затравки возвращают нулевое число совпадений для удлиненной затравки. Такие наборы результатов с нулем совпадений могут возникать, если удлиненная затравка включает такой вариант, как однонуклеотидный полиморфизм (SNP), или если удлиненная затравка выходит за край чтения, которому соответствует эта удлиненная затравка. Если такой сценарий происходит для каждой позиции затравки в чтении при использовании традиционных способов, чтение может быть некартированным.

[0049] Во-вторых, традиционные способы, как правило, могут быть связаны с «проблемой высокодостоверного неправильного картирования». Такие проблемы высокодостоверного неправильного картирования возникают, когда удлиненная затравка включает такой вариант, как SNP, но все же совпадает с одним или более позициями эталона. Такие сопоставления могут характеризоваться высоким показателем достоверности, таким как высокий показатель MAPQ, даже если удлиненная затравка картирована неправильно. Если это происходит для каждой позиции затравки в чтении с использованием традиционных способов, чтение может быть неправильно картировано, возможно, с высокой достоверностью. Для таких картирований доказательства противоположного могут быть упущены. Высокодостоверные неправильные картирования могут наносить больший ущерб точности системы картирования, чем неправильные картирования с низкой достоверностью. Показатель MAPQ может включать оценку качества, которая количественно определяет вероятность неверного положения картированного чтения.

[0050] В-третьих, традиционные способы могут сталкиваться с проблемой «фиксированного максимального числа совпадений». Как правило, в хеш-таблицах, составленных для удлинения затравки, используют параметр M максимального числа совпадений, такой как M=16. Этот параметр гарантирует, что ни один концевой узел дерева удлинения затравки не превысит параметр M. Однако в некоторых областях применения может быть полезно использовать другой параметр M* максимального числа совпадений, например M=64. Традиционные способы удлинения затравки будут продолжать итеративно удлинять затравку до достижения концевого узла. Соответственно, при применении традиционных способов удлинение затравок может не остановиться при достижении набора совпадений M=64, если хеш-таблица не была перестроена с обеспечением параметра M максимального числа совпадений, равного 64.

[0051] Передовые аспекты настоящего описания можно использовать для осуществления гибкого удлинения затравки с обеспечением возможности (i) снижения затраты вычислительных ресурсов и энергии, как описано в настоящем документе, и (ii) решения проблем традиционных способов удлинения затравки, например проблем, описанных в настоящем документе. Для достижения этих преимуществ в настоящем описании обеспечена, среди прочего, «запись об интервале», которая может храниться в некоторой позиции хеш-таблицы. Запись об интервале идентифицирует непрерывный набор совпадающих с конкретной затравкой позиций эталонной последовательности, хранящийся в таблице удлинений затравки, для конкретной затравки. После выполнения хеш-запроса, идентифицирующего конкретную затравку, блок картирования и выравнивания может определять на основе хеш-позиции, служащей ответом на запрос, следует ли (i) удлинять затравку на основе записи об удлинении затравки, хранящейся в данной хеш-позиции, (ii) сохранить запись об интервале, которая идентифицирует совпадающие с конкретной затравкой позиции эталона, в таблице удлинений затравки, или (iii) обращаться к позициям эталонной последовательности в таблице удлинений затравки, идентифицированным по записи об интервале, хранящейся в позиции хеша. В некоторых вариантах осуществления может быть выполнена комбинация этих операций, например удлинение затравки и хранение интервала.

[0052] Таким образом, за счет использования записи об интервале в сочетании с одной или более записями об удлинении модуль картирования и выравнивания уменьшает число совпадающих позиций, которые должен обрабатывать блок картирования и выравнивания посредством удлинения затравки, а также обеспечивает блок картирования и выравнивания гибкостью при определении, точны ли совпадающие с эталоном позиции, выявленные с помощью динамического удлинения затравки, или в некоторых случаях нужно ли вообще производить удлинение затравки с использованием одной или более записей об удлинении. В результате блок картирования и выравнивания использует меньше энергии и меньше вычислительных ресурсов, но при этом более точен, чем другие блоки картирования и выравнивания, в которых используют традиционные способы удлинения затравки.

Генерирование индекса хеш-таблицы для гибкого удлинения затравки

[0053] На ФИГ. 1 представлена контекстная схема системы 100 для генерирования индекса хеш-таблицы, облегчающей гибкое удлинение затравки для геномного картирования на основе хеш-таблицы. Система 100 включает в себя компьютер 110, память 112 и память 130. Хотя память 112 и память 130 показаны на ФИГ. 1 как отдельные запоминающие устройства, настоящее описание не обязательно ограничивается этим. Вместо этого в некоторых вариантах осуществления память 112 и память 130 могут представлять собой одно и то же запоминающее устройство. Например, память 112 и память 130 просто относятся к двум отдельным местам для хранения на одном запоминающем устройстве. В альтернативном варианте осуществления каждая из памяти 112 и памяти 130 соответственно может храниться на отдельных запоминающих устройствах, таких как отдельные жесткие диски, к которым имеет доступ компьютер 110. В качестве другого примера память 112 может представлять собой запоминающее устройство облачного сервера, на котором хранится библиотека эталонных геномов, а память 130 может представлять собой локальную память компьютера 110. Соответственно, изображение памяти 112 и памяти 130 в виде отдельных запоминающих устройств на ФИГ. 1 не накладывает никаких ограничений на сами устройства памяти 112, 130 или на содержимое этих устройств памяти, и не требует, чтобы эти устройства памяти были организованы или сохранены в каком-либо конкретном варианте реализации настоящего описания.

[0054] Компьютер 110 может включать в себя компьютер или множество компьютеров, каждый из которых включает в себя один или более блоков обработки, выполненных с возможностью осуществления операций путем выполнения одной или более программных команд. Один или более блоков обработки могут включать в себя один или более центральных процессоров (ЦП), один или более графических процессоров (ГП) или любую их комбинацию. Компьютер 110 может быть выполнен с возможностью взаимодействия с памятью 112, памятью 130 или программируемой схемой 162 напрямую, через прямое соединение, такое как одна или более шин, один или более кабелей USB, один или более кабелей USB-C и т.п. или любая их комбинация. В альтернативном или дополнительном варианте осуществления компьютер 110 может быть выполнен с возможностью взаимодействия с памятью 112, памятью 130 или программируемой схемой 162 через одну или более сетей. Одна или более сетей могут включать в себя проводную сеть Ethernet, беспроводную сеть, оптическую сеть, сеть LAN, сеть WAN, сотовую сеть, Интернет или любую их комбинацию.

[0055] В качестве примера один вариант реализации может включать в себя компьютер 110, выполненный с возможностью (i) взаимодействия с памятью 112 и памятью 130, хранящихся в одном или более локальных запоминающих устройствах, доступных для компьютера 110, для создания таблицы 132 удлинений затравки и хеш-таблицы 140, и (ii) передачи созданной таблицы 132 удлинений затравки и хеш-таблицы 140 в программируемую схему 162, интегрированную с другим устройством 160, с помощью одной или более сетей. Другое устройство 160 может включать в себя секвенатор нуклеиновых кислот, облачный(-ые) сервер(-ы) или любой другой компьютер. В некоторых вариантах осуществления программируемая схема 162 может быть интегрирована с другим устройством с помощью карты расширения, такой как карта PCI. В таких вариантах осуществления программируемая схема 162 может размещаться на логической плате карты PCI, вставляемой в материнскую плату секвенатора, облачного сервера или другого компьютера с использованием порта PCI на материнской плате.

[0056] Программируемая схема 162 может включать в себя одну или более программируемых интегральных схем, таких как одна или более программируемых пользователем вентильных матриц (FPGA). Программируемые пользователем интегральные схемы представляют собой интегральные схемы, которые включают в себя множество аппаратных цифровых логических вентилей, аппаратных цифровых логических схем или т.п., которые выполнены с возможностью динамического конфигурирования для реализации одного или более модулей обработки, таких как модули геномного анализа в канале геномного анализа, например блок 170 картирования и выравнивания, или часть модуля обработки, такой как хеш-таблица 140. FPGA может быть запрограммирована с использованием языка описания аппаратных средств (HDL), такого как язык описаний высокоскоростных интегральных схем (VHDL), Verilog или т.п. FPGA обладает гибкостью в том смысле, что FPGA, ранее запрограммированную включением в нее одного или более модулей геномного анализа из канала для геномного анализа или их частей, можно динамически переконфигурировать с включением в нее обновлений одного или более модулей геномного анализа, других различных модулей геномного анализа или т.п.

[0057] Для реализации функциональных возможностей программируемой схемы 162, описанной в настоящем документе, вместо программируемой схемы 162 или в дополнение к ней можно использовать другие типы интегральных схем. Например, одна или более специализированных интегральных схем (ASIC) могут быть использованы для реализации функциональных возможностей или части функциональных возможностей программируемой схемы 162. ASIC представляют собой специализированные интегральные схемы, которые включают в себя множество аппаратных цифровых логических вентилей, множество цифровых логических схем или т.п., которые настроены в процессе изготовления. ASIC похожи на FPGA, описанные в настоящем документе, тем, что аппаратные цифровые логические вентили или множество цифровых логических схем ASIC могут быть описаны или спроектированы с использованием языка описания аппаратного обеспечения, такого как VHDL, Verilog или т.п. Затем может быть изготовлена или напечатана ASIC, включающая в себя цифровую логику или цифровую схему, описанную на HDL. Однако после изготовления или печати конфигурацию ASIC нельзя динамически изменять, как FPGA. Хотя примеры, описанные в настоящем документе, описывают программируемые или специализированные схемы, настоящее описание не должно ограничиваться таким образом. Например, в некоторых вариантах осуществления для реализации функциональных возможностей, описанных как выполняемые программируемой схемой 162, можно использовать другие типы интегральных схем.

[0058] В памяти 112 может храниться одна или более эталонных последовательностей 114. Эталонная последовательность может включать в себя (i) весь эталонный геном, характерный для вида, (ii) участок эталонного генома, характерного для вида, или (iii) полные и/или частичные эталонные геномы, характерные для множества видов. Эталонная последовательность включает в себя последовательный перечень оснований или нуклеотидов. Последовательный перечень оснований или нуклеотидов, из которых состоит эталонная последовательность, может быть организован в памяти 112 в виде цифровой базы данных нуклеотидной последовательности. Конкретная эталонная последовательность может быть собрана лицами и/или компьютерами от множества разных доноров конкретного биологического вида, в качестве характерной для вида.

[0059] В некоторых вариантах осуществления конкретную эталонную последовательность можно собирать как характерную для конкретной популяции, причем конкретная популяция представляет собой подмножество из биологического вида, имеющее определенные нуклеотидные последовательности, которые могут однозначно отличать эту конкретную популяцию от других популяций в пределах вида. Вид может включать любые виды, в том числе людей, не относящихся к человеку млекопитающих, рептилий, рыб, насекомых, растения, бактерии, вирусы или т.п. Эталонная последовательность может быть получена из образцов от невымерших видов, например людей, или от вымерших видов, таких как популяция динозавров или мамонтов. Эталонные последовательности вымерших видов, таких как динозавр, можно собирать с использованием образцов, полученных из биологического материала, содержащегося в окаменелых, замороженных или иным образом сохранившихся останках вымерших видов. Эталонные последовательности от вымерших видов можно собирать путем комбинации (i) секвенирования биологических останков, полученных из окаменевших останков вымерших видов, и (ii) секвенирования биологических образцов от невымерших видов. Весь эталонный геном может включать множество последовательных оснований или нуклеотидов. Например, эталонный геном человека может включать до 3 миллиардов последовательных оснований или нуклеотидов.

[0060] Компьютер 110 выполнен с возможностью генерирования хеш-таблицы 140, которая упрощает гибкое удлинение затравки. Компьютер 110 начинает генерировать хеш-таблицу 140 посредством доступа к эталонной последовательности 114, хранящейся в памяти 112 и получения затравки 114-1, 114-2, 114-3 до 114-n из эталонной последовательности, причем n представляет собой любое ненулевое целое число больше нуля. В некоторых вариантах осуществления компьютер 110 может идентифицировать и получать затравку 114-1, 114-2, 114-3 до 114-n из эталонной последовательности 114 с использованием окна доступа к затравке. Компьютер 110 может инициализировать окно доступа к затравке значением длины затравки K, где K - количество оснований или нуклеотидов, подлежащих включению в каждую затравку, причем K - любое ненулевое целое число больше нуля. Компьютер 110 может начинать обращаться к затравкам в эталонной последовательности 114 посредством размещения окна доступа к затравке длиной K в начале эталонной последовательности с обеспечением включения первого набора из K нуклеотидов в эталонной последовательности, например затравки GTTTA 114-1. В этом примере K равно 5, но K не ограничивается таким количеством нуклеотидов. Напротив, K может быть равно любому ненулевому целому числу больше нуля, а в некоторых вариантах осуществления может быть равно, например, 7, 10, 12, 15, 18, 20, 21, 25 или более оснований или нуклеотидов. Затравки 114-1, 114-2, 114-3 до 114-n являются лишь примерами затравок из эталонной последовательности 114, и в этом примере не обязательно должны соответствовать набору из 4 последовательных затравок эталонной последовательности 114.

[0061] Для генерирования хеш-таблицы 140 компьютер 110 выполнен с возможностью доступа к каждой затравке 114-1, 114-2, и от 114-3 до 114-n эталонной последовательности 114 и выполнения набора операций для каждой затравки 114-1, 114-2, и от 114-3 до 114-n. Набор операций выполнен с возможностью формирования информации, хранящейся в хеш-позициях 144 хеш-таблицы 140, соответствующих индексным ключам 142 хеш-таблицы 140. Каждый индексный ключ 142 может соответствовать соответствующей затравке из множества затравок 114-1, 114-2, 114-3 до 114-n эталонной последовательности 114, обратному комплементу каждой из затравок 114-1, 114-2, 114-3 до 114-n, удлиненной затравке из одной или более из множества затравок 114-1, 114-2, и от 114-3 до 114-n или обратному комплементу от каждой из удлиненных затравок. Каждую из проиндексированных затравок 142 можно сопоставлять с хеш-позицией 144 с помощью хеш-функции 143.

[0062] Компьютер 110 может идентифицировать каждую затравку из множества затравок 114-1, 114-2, 114-3 до 114-n и обращаться к ней путем продвижения окна доступа к затравке на K позиций эталонной последовательности 114 после обращения к каждой соответствующей затравке и ее использования для выполнения набора операций. Набор операций, выполняемых для каждой соответствующей затравки 114-1, 114-2, 114-3 по 114-n, более подробно описан ниже. Набор операций может включать заполнение хеш-таблицы 140 с использованием сгенерированной информации. В альтернативном варианте осуществления заполнение хеш-таблицы 140 может происходить после завершения набора операций для каждой затравки.

[0063] Набор операций, выполняемых компьютером 110 на каждой из затравок 114-1, 114-2, и от 114-3 по 114-n эталонной последовательности 114, начинается после получения компьютером 110 затравки, определяемой окном доступа к затравке. В примере на ФИГ. 1 предположим, что затравка эталонной последовательности 114, определяемая окном доступа к затравке, представляет собой GTTTA 114-1.

[0064] Компьютер 110 может определять, имеет ли полученная затравка GTTTA 114-1 превышающее заданное число количество совпадений с позициями эталонной последовательности 114. Совпадающая позиция эталонной последовательности может включать часть эталонной последовательности 114, которая включает затравку 114-1. Часть эталонной последовательности 114 может включать набор последовательно расположенных нуклеотидов, количество которых равно K нуклеотидам полученной затравки или более. В некоторых вариантах осуществления заданное число совпадающих позиций эталонной последовательности может включать одну совпадающую позицию эталонной последовательности. Однако в других вариантах осуществления заданное число может быть установлено равным более чем одной совпадающей позиции эталонной последовательности.

[0065] Если компьютер 110 определяет, что затравка 114-1 имеет число совпадений, равное заданному количеству позиций эталонной последовательности или менее, компьютер может заносить позицию(-и) эталона, совпадающую(-ие) с затравкой 114-1, в хеш-позицию 144, которую охватывает затравка GTTTA 114-1. Хеш-позиция 144 может быть «охвачена» затравкой, такой как затравка 114-1, если затравка 114-1 соответствует хеш-ключу 142, который хеш-функция 143 сопоставляет с хеш-позицией. В альтернативном варианте осуществления, если компьютер 110 определяет, что заданное количество совпадений позиций эталонной последовательности больше заданного количества позиций эталонной последовательности, компьютер 110 может генерировать дерево удлинения затравки для затравки 114-1. В примере на ФИГ. 1 компьютер 110 определяет, что затравка GTTTA 114-1 имеет превышающее заданное число количество совпадений с позициями эталонной последовательности. Соответственно, компьютер 110 генерирует дерево 120 удлинения затравки для затравки 114-1.

[0066] Компьютер 110 может генерировать дерево 120 удлинения затравки для затравки 114-1 узел за узлом, начиная от корневого узла 120. Дерево 120 удлинения затравки можно генерировать таким образом, чтобы набор совпадений с позициями эталона, идентифицированный концевым узлом, не превышал заданного предела по количеству совпадений, пока дополнительное удлинение затравки не окажется невозможным. Каждый узел дерева 120 удлинения затравки может включать затравку и интервал смежных адресов в таблице 132 удлинений затравки. В некоторых вариантах осуществления таблица 132 удлинений затравки включает центрально-лексикографически-отсортированный список позиций эталонной последовательности от 131-1 до 131-6, которые совпадают с затравкой, такой как затравка 114-1, полученной компьютером 110 с использованием окна доступа к затравке. Центральная лексикографическая сортировка может включать, например, установку порядка приоритета символов, а затем чередование положений слева и справа наружу от центрального символа. В альтернативном варианте осуществления центральная лексикографическая сортировка может включать в себя, например, установку порядка приоритета символов, а затем чередование положений справа и слева наружу от центрального символа. Однако можно использовать и другие варианты.

[0067] В примере на ФИГ. 1 таблица 132 удлинений затравки представляет собой центрально-лексикографическую сортировку 133 на основе затравки 114-1 GTTTA. В данном примере предполагается порядок «сначала слева» и обычный алфавитный порядок нуклеотидов (т.е. A, C, G, T) и получается центрально-лексикографический порядок сортировки, показанный на ФИГ. 1. Компьютер 110 может генерировать таблицу удлинений затравки, такую как таблица 132 удлинений затравки, для каждой затравки 114-1, 114-2, 114-3, 114-n, для которой определено, что число совпадений с позициями эталонной последовательности превышает заданное пороговое значение. В некоторых вариантах осуществления создавать таблицу 132 удлинений затравки можно для каждой проверяемой затравки после получения компьютером 110 доступа к конкретной затравке с помощью окна доступа к затравке и до создания дерева 120 удлинения затравки.

[0068] Приведенное выше описание узлов дерева 120 удлинения затравки показывает, что интервал адресов для каждого узла непрерывен. Тем не менее настоящее описание не обязательно ограничено таким образом. Вместо этого интервал адресов узла может не быть непрерывным. Например, в некоторых вариантах осуществления интервал можно использовать для описания множества разных наборов из одной или более смежных позиций таблицы удлинений затравки или другой структуры данных, хранящейся в одном или более запоминающих устройствах, где все непрерывные наборы из одной или более смежных позиций не смежны по отношению друг к другу. Таким образом, может существовать разрыв непрерывности между соответствующими наборами.

[0069] Таблица удлинений затравки для каждой проверяемой затравки может храниться в памяти 130. В результате могут быть получены n таблиц удлинений затравки - т.е. по одной для каждой из n затравок эталонной последовательности 114. В альтернативном варианте осуществления число таблиц удлинений затравки может быть меньше n, например при генерирования и хранении таблиц удлинений затравки только для затравок, имеющих число совпадающих позиций эталонной последовательности, превышающее заданное пороговое число. После генерирования каждой из таблиц удлинений затравки каждый набор 132A таблиц удлинений затравки может быть передан устройству 160, содержащему программируемую схему 162, и может храниться в памяти 180, доступной для программируемой схемы 162. Память 180 может включать DRAM-память, SRAM-память, NAND-память или т.п. В некоторых вариантах осуществления набор 132A таблиц удлинений затравки может быть передан устройству 160, содержащему программируемую схему 162 в виде индивидуальных таблиц удлинений затравки. В других вариантах осуществления набор 132A таблиц удлинений затравки может быть передан в виде единой главной таблицы удлинений затравки, сформированной путем соединения всех соответствующих таблиц удлинений затравки для каждой затравки. Набор 132A таблиц удлинения затравок может быть передан в любом количестве форматов. В некоторых вариантах осуществления набор 132A таблиц удлинений затравки может быть сжат компьютером 110 для уменьшения размера файла таблиц удлинений затравки, передаваемого в устройство 160, а затем распакован устройством 160, программируемой схемой 162 или т.п. для хранения в памяти 180.

[0070] Компьютер 110 может генерировать корневой узел 121 дерева 120 удлинения затравки посредством включения в него затравки GTTTA 121a и интервала A 121b. Интервал A 121b идентифицирует непрерывный интервал позиций в таблице 132 удлинений затравки, в котором хранятся позиции эталонной последовательности, совпадающие с затравкой GTTTA 121а, представленной корневым узлом 121. В данном примере интервал A определяет позицию таблицы 132 удлинений затравки, охватывающую пункты от 131-1 до 132-6 и включающую последовательности TAGTTTACT, TAGTTTATC, GAGTTTATG, ACGTTTAGT, TCGTTTAGT и ACGTTTAGC. Компьютер 110 может определять подходящий интервал или интервалы для конкретной затравки узла, такого как узел 121, обращаясь к таблице 132 удлинений затравки, и определять позиции в таблице 132 удлинений затравки, содержащие позиции эталонной последовательности, совпадающие с затравкой узла 121.

[0071] В некоторых вариантах осуществления интервал 121b для конкретной затравки узла, такого как узел 121, может быть описан с использованием адреса начала интервала в таблице 132 удлинений затравки и адреса конца интервала в таблице 132 удлинений затравки. В других вариантах осуществления интервал 121b для конкретной затравки узла, такого как узел 121, может быть описан с использованием адреса начала интервала в таблице 132 удлинений затравки и смещения от адреса начала. В таких вариантах осуществления интервал может позднее быть вычислен с использованием начальных и конечных адресов интервала или адреса начала интервала и смещения. Тем не менее настоящее описание не обязательно ограничено таким образом. Напротив, следует понимать, что запись об интервале может быть представлена в позиции 144 хеш-таблицы с использованием любой формы информации, структурированной любым подходящим способом или неструктурированной. Например, в некоторых вариантах осуществления запись об интервале может быть реализована с использованием одной записи фиксированного размера и формата. В других вариантах осуществления запись об интервале может быть реализована путем выбора среди множества форматов разных размеров, содержащих количество записей или т.п., для оптимизации пространства для хранения, используемого хеш-таблицей 140, обеспечения возможности сжатия хеш-таблицы 140, повышения эффективности хеш-запросов по сравнению с другими форматами записей об интервалах или т.п.

[0072] Компьютер 110 может продолжать генерирование дерева 120 удлинения затравки путем увеличения числа оснований или нуклеотидов для затравки 121а, идентифицированной в корневом узле. Например, компьютер 110 может увеличивать длину затравки корневого узла на величину от 5 оснований или нуклеотидов до 7 оснований или нуклеотидов и идентифицировать в таблице удлинений затравки наибольший набор позиций эталонной последовательности, имеющих 7 совпадающих оснований или нуклеотидов. В примере на ФИГ. 1 компьютер 110 может определять, что наибольший набор позиций эталонной последовательности, имеющий 7 совпадающих нуклеотидов, представляет собой CGTTTAG. Интервал B идентифицирует в таблице 132 удлинений затравки непрерывный интервал позиций, в котором хранятся позиции эталонной последовательности, совпадающие с затравкой CGTTTAG. В данном примере интервал B показывает идентифицирует позицию таблицы 132 удлинений затравки, охватывающую пункты от 132-4 до 132-6 и включающую последовательности ACGTTTAGT, TCGTTTAGT и ACGTTTAGC. Компьютер 110 может генерировать узел 122 с использованием информации, определенной с помощью таблицы 132 удлинений затравки. Например, компьютер 110 может генерировать узел 122 и включать в него затравку CGTTTAG 122a и интервал B 122b.

[0073] Как показано в примере на ФИГ. 1, компьютер 110 может продолжать генерирование дерева 120 удлинения затравки путем определения наличия в таблице удлинений затравки других позиций эталонной последовательности, имеющих 7 совпадающих оснований или нуклеотидов. Если в таблице 132 удлинений затравки имеются другие позиции эталонной последовательности, имеющие 7 совпадающих оснований или нуклеотидов, компьютер 110 использует следующий наибольший набор позиций эталонной последовательности, имеющий 7 совпадающих оснований или нуклеотидов, для создания следующего узла дерева удлинения затравки. В примере на ФИГ. 1 компьютер 110 может определять, что следующий наибольший набор позиций эталонной последовательности, который имеет 7 совпадающих нуклеотидов, представляет собой AGTTTAT. Интервал E идентифицирует непрерывный интервал позиций в таблице 132 удлинений затравки, в котором хранятся позиции эталонной последовательности, совпадающие с затравкой AGTTTAT. В данном примере интервал E указывает позицию в таблице 132 удлинений затравки, которая охватывает диапазон от 132-2 до 132-3 и включает последовательности TAGTTTATC и GAGTTTATG. Компьютер 110 может генерировать узел 123 с использованием информации, определенной с помощью таблицы 132 удлинений затравки. Например, компьютер 110 может генерировать узел 123 с включением в него затравки AGTTTAT 123a и интервала E 123b.

[0074] Как показано в примере на ФИГ. 1, компьютер 110 может продолжать генерирование дерева 120 удлинения затравки путем определения наличия в таблице удлинений затравки других позиций эталонной последовательности, имеющих 7 совпадающих оснований или нуклеотидов. Если в таблице удлинений затравки идентифицированы другие позиции эталонной последовательности, имеющие 7 совпадающих оснований или нуклеотидов, компьютер 110 может генерировать новый узел таблицы 120 удлинений затравки с использованием следующего наибольшего набора позиций эталонной последовательности, имеющих 7 совпадающих оснований или нуклеотидов, как описано выше. Однако в примере, показанном на ФИГ. 1, в таблице 132 удлинений затравки отсутствуют другие позиции эталонной последовательности, имеющие 7 совпадающих оснований или нуклеотидов. Соответственно, компьютер 110 может определять необходимость увеличения числа оснований нуклеотидов с 7 до 9 и продолжать анализ позиций эталонной последовательности в таблице 132 удлинений затравки.

[0075] Как показано в примере на ФИГ. 1, компьютер 110 может выявлять наибольший набор позиций эталонной последовательности, имеющих 9 совпадающих нуклеотидов. В данном примере имеется множество наборов позиций эталонной последовательности, имеющих 9 совпадающих нуклеотидов. В таких случаях компьютер 110 может решать создать узел дерева удлинения затравки для каждого набора позиций эталонной последовательности, имеющего 9 совпадающих нуклеотидов эталонной последовательности. В некоторых вариантах осуществления компьютер 110 может определять порядок создания узлов дерева удлинения затравки случайным образом. В других вариантах осуществления компьютер 110 может начинать генерировать последующие узлы дерева удлинений на основе их центрального лексикографического порядка.

[0076] Независимо от порядка создания, компьютер 110 может продолжать генерирование узлов таблицы удлинений затравки для каждого набора позиций эталонной последовательности, имеющего 9 совпадающих нуклеотидов. Например, компьютер 110 может генерировать узел 124 дерева 120 удлинения затравки и включать в него удлиненную короткую затравку TCGTTTAGT 124a и интервал C 124b. Интервал C 124b идентифицирует непрерывный интервал позиций в таблице 132 удлинений затравки, в котором хранятся позиции эталонной последовательности, совпадающие с короткой затравкой TCGTTTAGT 124a. В данном примере интервал C идентифицирует позицию таблицы 132 удлинений затравки, которая охватывает 132-5 и включает последовательность TCGTTTAGT. Компьютер 110 может определять подходящий интервал для конкретной короткой затравки узла, такого как узел 124, с помощью таблицы 132 удлинений затравки и определять позиции в таблице 132 удлинений затравки, содержащие позиции эталонной последовательности, совпадающие с затравкой узла 124.

[0077] Как показано в примере на ФИГ. 1, компьютер 110 может продолжать генерирование узлов таблицы удлинений затравки для каждого набора позиций эталонной последовательности, имеющего 9 совпадающих нуклеотидов. Например, компьютер 110 может генерировать узел 125 дерева 120 удлинения затравки и включать в него удлиненную короткую затравку ACGTTTAGC 125a и интервал D 125b. Интервал D 125b идентифицирует непрерывный интервал позиций в таблице 132 удлинений затравки, в котором хранятся позиции эталонной последовательности, совпадающие с короткой затравкой ACGTTTAGC 125a. В данном примере интервал D идентифицирует позицию таблицы 132 удлинений затравки, которая охватывает пункт 132-6 и включает последовательность ACGTTTAGC. Компьютер 110 может определять подходящий интервал для конкретной короткой затравки узла, такого как узел 125, с помощью таблицы 132 удлинений затравки и определять позиции в таблице 132 удлинений затравки, содержащие позиции эталонной последовательности, совпадающие с затравкой узла 125.

[0078] Как показано в примере на ФИГ. 1, компьютер 110 может продолжать генерирование узлов таблицы удлинений затравки для каждого набора позиций эталонной последовательности, имеющего 9 совпадающих нуклеотидов. Например, компьютер 110 может генерировать узел 126 дерева 120 удлинения затравки и включать в него удлиненную короткую затравку TAGTTTATC 126a и интервал F 126b. Интервал F 126b идентифицирует непрерывный интервал позиций в таблице 132 удлинений затравки, в котором хранятся позиции эталонной последовательности, совпадающие с короткой затравкой TAGTTTATC 126a. В данном примере интервал F идентифицирует позицию таблицы 132 удлинений затравки, которая охватывает пункт 132-2 и включает последовательность TAGTTTATC. Компьютер 110 может определять подходящий интервал для конкретной короткой затравки узла, такого как узел 126, с помощью таблицы 132 удлинений затравки и определять позиции в таблице 132 удлинений затравки, содержащие позиции эталонной последовательности, совпадающие с затравкой узла 126.

[0079] В настоящем описании представлен пример построения таблицы удлинений затравки в определенном методическом порядке, который идет от наибольшего набора совпадающих оснований к наименьшему набору совпадающих оснований. Однако настоящее описание не должно ограничиваться использованием деревьев удлинения затравок, построенных таким образом. Напротив, можно использовать любой процесс построения таблицы удлинений затравки при условии, что в результате процесса построения таблицы удлинений затравки получают таблицу удлинений затравки. Например, дерево удлинения затравки можно генерировать от наименьшего набора совпадающих оснований к наибольшему набору совпадающих оснований, или вообще без конкретного порядка. В некоторых вариантах осуществления предварительно генерируемая таблица удлинений затравки может быть создана и может быть использована системой 100 без необходимости построения таблицы удлинений затравки системой 100.

[0080] Компьютер 110 может заполнять хеш-позиции 144 хеш-таблицы 140, охватываемые конкретными входными затравками, которые соответствуют конкретным индексным ключам 142 хеша, с помощью созданного дерева 120 удлинения затравки. Например, компьютер 110 может определять, является ли узел 121 концевым узлом. На основании определения, что узел 121 не является концевым узлом, компьютер 110 может заполнять хеш-позицию 144-y, с помощью корневого узла 121, где y - любое ненулевое целое число. Заполнение хеш-позиции 144-y с использованием корневого узла 121 может включать в себя хранение записи 153b об интервале в позиции 144-y хеш-таблицы, охватываемой затравкой 121a. Запись 153b об интервале идентифицирует интервал 121b для узла 121. Хеш-таблица 140 может включать индексный ключ 142 хеш-таблицы для каждой затравки 114-1, 114-2, 114-3 до 114-n, обратного комплемента каждой затравки 114-1, 114-2, 114-3 до 114-n или их комбинации. Каждый индексный ключ 142 хеш-таблицы может быть сопоставлен с одной или более хеш-позициями 144 с помощью хеш-функции 143. Каждая хеш-позиция 144 может быть реализована с использованием одной или более корзин хранения, причем корзина для хранения соответствует набору из одной или более позиций хранения на запоминающем устройстве. Каждая из одной или более позиций хранения на запоминающем устройстве может представлять собой смежные или несмежные позиции в памяти.

[0081] В примере на ФИГ. 1 показана только часть хеш-таблицы 140, имеющей ключи 142, и соответствующей прямой затравке из затравок 121, 122, 123 и 125. Тем не менее настоящее описание не обязательно ограничено таким образом. Например, в некоторых вариантах осуществления затравки могут быть хешированы с применением хеш-функции 143 таким образом, что нуклеотидная последовательность обратного комплемента любой затравки дает тот же хеш, что и первоначальная прямая затравка. Обратный комплемент нуклеотидной последовательности может быть определен путем обращения порядка исходной нуклеотидной последовательности и замены всех A на T, T на A, C на G и G на C. Например, хеш-ключ 142 для первоначальной прямой затравки GTTTA 121a может иметь такой же хеш, что и хеш-ключ 142 обратного комплемента затравки GTTTA, который представляет собой TAAAC. В таких вариантах осуществления, если совпадающие позиции эталонной последовательности хранятся в хеш-позиции 144 или в виде записей в таблице 132 удлинений затравки, ориентацию их последовательности можно аннотировать с применением, например, флага обратного комплемента (RC). Однако в других вариантах осуществления обратный комплемент затравки может давать другой хеш, и при этом не требуется аннотировать ориентацию совпадающих позиций эталонной последовательности, хранящихся в хеш-позиции 144 хеш-таблицы 140 или в таблице 132 удлинений затравки.

[0082] Заполнение позиции 144 хеш-таблицы 140 может также включать определение, нужно ли загружать в хеш-позицию 144 запись об удлинении. Определение, следует ли загружать запись об удлинении в хеш-позицию 144, может включать определение, является ли узел дерева 120 удлинения затравки, используемый для заполнения хеш-позиции, концевым узлом. Если определено, что узел является концевым узлом, компьютер 110 может принимать решение не хранить запись об удлинении в хеш-позиции, охватываемой затравкой, ассоциированной с узлом. В альтернативном варианте осуществления, если определено, что узел не является концевым узлом, компьютер 110 может генерировать запись об удлинении и хранить сгенерированную запись об удлинении в позиции 144 хеш-таблицы. Как показано в примере на ФИГ. 1, компьютер 110 может определять или предварительно определять, что узел 121 не является концевым узлом. В таких случаях компьютер 110 может генерировать и хранить запись 153a об удлинении в хеш-позиции 144-y, охватываемой затравкой 121a. Соответственно, хеш-позиция 144-y может включать запись 153a об удлинении и запись 153b об интервале.

[0083] Запись об удлинении может включать одну или более команд, при исполнении которых компьютером, таким как центральный процессор (ЦП) или графический процессор (ГП), исполняющим программные команды, или программируемая схема 162, ЦП, ГП или программируемая схема 162 могут удлинять затравку, использованную в хеш-запросе, охватившем хеш-позицию, хранящую запись об удлинении, на один или более нуклеотидов. В некоторых вариантах осуществления запись об удлинении может быть сгенерирована таким образом, чтобы запись об удлинении давала команду компьютеру симметрично удлинять затравку с каждого конца затравки. Соответственно, в качестве примера может быть сгенерирована запись об удлинении, дающая команду компьютеру, такому как ЦП, ГП или программируемая схема 162, удлинять затравку на два нуклеотида, четыре нуклеотида, шесть нуклеотидов или т.п. В таких вариантах осуществления симметричное удлинение затравки может быть достигнуто путем удлинения затравок на один нуклеотид на каждом соответствующем конце затравки, на два нуклеотида на каждом соответствующем конце затравки, на три нуклеотида на каждом соответствующем конце затравки или т.п. В примере на ФИГ. 1 запись 153a об удлинении выполнена с возможностью симметричного удлинения исходной затравки 121a на 2 основания. Компьютер 110 может определять длину удлинения для включения в запись об удлинении на основании разнообразных факторов, к которым относятся (i) количество позиций эталонной последовательности, совпадающих с затравкой, (ii) количество требуемых итераций оперативного удлинения затравки, (iii) количество искомых совпадающих позиций эталонной последовательности в каждой итерации, или т.п. Гибкое оперативное удлинение затравки с использованием хеш-таблицы 140 описано ниже более подробно со ссылкой на ФИГ. 3.

[0084] Затравки нуклеотидов по существу описаны как состоящие из смежных наборов последовательных нуклеотидов. Аналогичным образом записи об удлинении описаны как последовательно удлиняющие непрерывный набор последовательных нуклеотидов на один или более дополнительных нуклеотидов способами, которые могут быть симметричными или асимметричными, но с сохранением непрерывности. Однако настоящее описание не ограничено использованием непрерывных наборов последовательных нуклеотидов. Напротив, затравки чтения или эталонной последовательности могут представлять собой несмежные структуры затравок из чтения или из эталонной последовательности. Аналогичным образом запись об удлинении может включать команды, при обработке которых с помощью ЦП, ГП или программируемой схемы 162, ЦП, ГП или программируемая схема 162 удлиняет исходную затравку с включением несмежных ближайших оснований или нуклеотидов. В таких вариантах осуществления совпадающие позиции эталонной последовательности для каждого корневого узла затравки могут быть отсортированы в таблице 132 удлинений затравки лексикографическим способом с учетом использования несмежных затравок.

[0085] Компьютер 110 может продолжать загрузку информации в хеш-позиции 144 для всех остальных узлов 122, 123, 124, 125, 126 дерева 120 удлинения затравки. Например, компьютер 110 может определять, является ли узел 122 концевым узлом. На основании определения, что узел 122 не является концевым узлом, компьютер 110 может заполнять хеш-позицию 144-3 с помощью узла 122. Заполнение хеш-позиции 144-3 с использованием узла 122 может включать в себя хранение записи 152b об интервале в позицию 144-3 хеш-таблицы, которую охватывает затравка 122a. Запись 152b об интервале идентифицирует интервал 122b для узла 122. Компьютер 110 может определять или предварительно определять, что узел 122 не является концевым узлом, и генерировать запись 152a об удлинении для хранения в хеш-позиции 144-3. В примере на ФИГ. 1 запись 152a об удлинении включает команды по симметричному удлинению затравки 122a на 2 основания или нуклеотида. Эти команды из записи 152а об удлинении могут быть выполнены в оперативном режиме, если, например, в ответ на запрос с затравкой 122а доступ к интервалу B не получен.

[0086] Однако представленное описание этим не ограничено, так как может также быть сгенерирована другая запись об удлинении, которая дает команду ЦП, ГП или программируемой схеме 162 удлинить затравку на иное дополнительное количество нуклеотидов (например, 2, 4, 6, 8 и т.д.) или иными способами (например несимметричное использование дополнительного числа нуклеотидов 1, 3, 5 и т.д.). В примере на ФИГ. 1 представлена одна запись об удлинении в хеш-позиции 144-3, причем настоящее описание не ограничено таким образом. Напротив, в некоторых вариантах осуществления в одной хеш-позиции 144-3 может храниться множество записей об удлинении. Например, компьютер 110 может также хранить одну или более дополнительных записей об удлинении в хеш-позиции 144-3, которые выполнены с возможностью удлинения первоначальной затравки 122a на четыре основания. В таких вариантах осуществления ЦП, ГП или программируемая схема 162 в оперативном режиме может сначала пытаться удлинять первоначальную затравку 122a на четыре основания. В случае неудачи при таком удлинении затравки из-за того, что последующий запрос к хеш-таблице 140 в оперативном режиме не дает совпадений позиций эталонной последовательности, ЦП, ГП или программируемая схема могут получать другую запись 152a об удлинении, которая включает команды по удлинению исходной затравки всего на 2 основания. Таким образом можно повышать вероятность получения совпадений с позициями эталонной последовательности.

[0087] Компьютер 110 может продолжать ввод информации в хеш-позиции 144 для каждого узла 123, 124, 125, 126 дерева 120 удлинения затравки. Например, компьютер может определять, является ли узел 123 концевым узлом. На основании определения, что узел 123 не является концевым узлом, компьютер 110 может заполнять хеш-позицию 144-1 с помощью узла 123. Заполнение хеш-позиции 144-1 может включать в себя хранение записи 150b об интервале в позицию 144-1 хеш-таблицы, которую охватывает затравка 123a. Запись 150b об интервале идентифицирует интервал 123b для узла 123. Компьютер 110 может определять или предварительно определять, что узел 123 не является концевым узлом, и генерировать запись 150a об удлинении для хранения в хеш-позиции 144-1. В данном примере запись 150a об удлинении включает команды по симметричному удлинению затравки 123a на 2 основания или нуклеотида. Эти команды из записи 150а об удлинении могут быть выполнены в оперативном режиме, если, например, в ответ на запрос с затравкой 123а нет обращения к интервалу E.

[0088] Компьютер 110 может продолжать ввод информации в хеш-позиции 144 для каждого узла 124, 125, 126 дерева 120 удлинения затравки. Например, компьютер 110 может определять, является ли узел 125 концевым узлом. На основании определения, что узел 125 является концевым узлом, компьютер 110 может принимать решение о заполнении хеш-таблицы 140 путем хранения совпадающих позиций 155 эталонной последовательности, идентифицированных интервалом D 125b, которые совпадают с затравкой ACGTTTAGC, в хеш-позиции 144-2. В альтернативном варианте осуществления в других реализациях компьютер 110 может принимать решение хранить в хеш-позиции 144-2 запись об интервале, которую идентифицирует интервал D 125b. В некоторых вариантах осуществления такое решение может быть принято компьютером 110 на основании того, является ли хранение всех совпадающих позиций эталонной последовательности в позициях хеш-таблицы 144 для концевых узлов оптимальным использованием ресурсов памяти. Соответственно, если определено, что хранение совпадающих позиций эталонной последовательности в позициях хеш-таблицы 144 для концевых узлов не удовлетворяет заданному пороговому использованию ресурсов памяти, компьютер 110 может хранить совпадающие позиции эталонной последовательности в хеш-позициях, охватываемых затравками концевого узла дерева удлинения затравки. Иначе, при превышении порога использования ресурсов памяти компьютер 110 может хранить запись об интервале в хеш-позициях 144, достигаемых затравками концевого узла дерева удлинения затравки. Компьютер 110 может определять или предварительно определять, что узел 125 является концевым узлом, и не генерировать запись об удлинении для хранения в хеш-позиции 144-2. Соответственно, в данном примере в оперативном режиме не происходит дополнительных удлинений затравки ACGTTTAGC.

[0089] Как описано выше, в хеш-позиции 144-2 могут храниться только совпадающие позиции эталонной последовательности, которые совпадают с затравкой 125a и соответствуют хеш-ключу 142-1. Это связано с тем, что в данном примере затравка 125a представляет собой затравку концевого узла 125, которая не может быть удлинена. Однако заполнение позиций эталонной последовательности без записи об удлинении и/или записи об интервале не ограничены хеш-позициями 144, охватываемыми затравками концевых узлов. Вместо этого компьютер 110 в других случаях может принимать решение заполнять хеш-позицию 144 совпадающими позициями эталонной последовательности без записи об удлинении и/или записи об интервале. Например, в некоторых вариантах осуществления, если компьютер 110 определяет, что таблица 132 удлинений затравки, относящаяся к конкретной затравке, идентифицирует только интервал совпадающих позиций эталонной последовательности, который меньше порогового числа совпадающих позиций эталонной последовательности, компьютер 110 может заполнять хеш-позицию 144, охватываемую конкретной затравкой, совпадающими позициями эталонной последовательности, без записи об удлинении и/или записи об интервале.

[0090] В хеш-позиции 144 хеш-таблицы 140 могут храниться и другие типы информации. Например, компьютер 110 может принимать команду по вставке одной или более записей типа «ОСТАНОВКА» в хеш-позицию 144 хеш-таблицы 140. При наличии такой хеш-записи «ОСТАНОВКА» конкретная хеш-позиция 140, в которой хранится запись об интервале или набор из одной или более совпадающих с эталоном позиций, может возвращать либо (i) запись об интервале, либо (ii) набор из одной или более совпадающих с эталоном позиций без дополнительного удлинения затравки, используемой для охвата данной хеш-позиции. В других вариантах осуществления компьютер 110 может принимать команду по вставке записи типа «ОСТАНОВКА» в хеш-позицию, которая уже включает запись об удлинении. В таких вариантах осуществления, когда ЦП, ГП или программируемая схема 162 встречается с записью «ОСТАНОВКА», ЦП, ГП, или программируемая схема 162 может условно определять, следует ли (i) игнорировать запись об удлинении и возвращать (i) запись об интервале или (ii) набор из одной или более совпадающих позиций эталона, которые совпадают с затравкой, использованной для охвата хеш-позиции, содержащей запись «ОСТАНОВКА», или (ii) выполнять удлинение затравки, описанное в записи об удлинении затравки. В некоторых вариантах осуществления условное определение можно осуществлять на основании одного или более факторов, таких как число совпадающих эталонных последовательностей, идентифицированных (i) записью об интервале или (ii) набором из одной или более совпадающих позиций эталонной последовательности. Соответственно, операции вставки для вставки одной или более записей типа «ОСТАНОВКА» в конкретные хеш-позиции в ответ на соответствующие входные затравки можно использовать в качестве конструктивного инструмента для предотвращения проблемы фиксированного максимального числа несовпадений без перестроения хеш-таблицы, такой как хеш-таблица 140.

[0091] Компьютер 110 может продолжать итерационное введение информации в хеш-позиции 144 для каждого оставшегося узла дерева 120 удлинения затравки, такого как узлы 124, 126. Пункты для каждого из этих концевых узлов могут быть заполнены способом, описанным выше в отношении узла 125, так как узлы 124, 126 являются концевыми узлами, подобными узлу 125.

[0092] Кроме того, компьютер 110 может продолжать применять описанные выше процессы итеративным образом в примере, показанном на ФИГ. 1 применительно к затравке GTTTA 114-1 для каждой затравки эталонной последовательности 114. Например, после обработки затравки GTTTA 114-1, как описано выше, компьютер 110 может продвигать окно доступа к следующей затравке в эталонной последовательности, выполнять доступ к затравке, и затем итеративно выполнять процессы, описанные выше применительно к затравке GTTTA 114-1, для каждой из n затравок эталонной последовательности. Эти процессы могут включать в себя получение затравки, идентифицированной окном доступа к затравке, определение, имеет ли затравка превышающее заданное число количество совпадений с позициями эталонной последовательности, формирование дерева удлинения затравки, если количество совпадений с позициями эталонной последовательности превышает заданное число, и затем заполнение хеш-таблицы 144 с использованием затравки и интервала, идентифицированных узлами дерева удлинения затравки. В некоторых вариантах осуществления компьютер 110 может также выполнять те же процессы в итеративном режиме, которые описаны выше применительно к затравке GTTTA 114-1, для обратного комплемента к каждой из n затравок эталонной последовательности 114. Завершение этих итеративных процессов для каждой эталонной затравки и каждого обратного комплемента может привести к получению хеш-таблицы 140, имеющей x индексных записей и y хеш-позиций, где каждый из x и y имеет порядок сотен миллионов или даже миллиардов для конкретной эталонной последовательности, такой как человеческий геном.

[0093] В некоторых вариантах осуществления хеш-таблицу 140 может использовать компьютер, такой как компьютер 110, для выполнения оперативного гибкого удлинения затравки путем выполнения хеш-запросов к хеш-таблице 140 в программном обеспечении с использованием одного или более ЦП, ГП или их комбинации, и выполнения программных команд, посредством которых один или более ЦП, ГП или их комбинация осуществляют процессы, описанные со ссылкой на ФИГ. 3 и 4. В других вариантах осуществления компьютер 110 может генерировать пакет для инсталляции хеш-таблицы, который включает в себя программные команды по установке хеш-таблицы 140 и набора 132A таблиц удлинений затравки на другом компьютере. Например, пакет для инсталляции хеш-таблицы может включать в себя программные команды, которые при исполнении осуществляют операции, описанные процессом 200, показанным на ФИГ. 2. Компьютер 110 может передавать пакет для инсталляции хеш-таблицы, который включает в себя программные команды, на другой компьютер. Другой компьютер может принимать пакет для инсталляции хеш-таблицы и устанавливать хеш-таблицу 140 и набор 132A таблиц удлинений затравки. Другой компьютер может далее выполнять оперативное гибкое удлинение затравок путем выполнения хеш-запросов к хеш-таблице 140 в программном обеспечении с использованием одного или более ЦП, ГП или их комбинации, и выполнения программных команд, посредством которых ЦП, ГП или их комбинация осуществляют процессы, описанные со ссылкой на ФИГ. 3 и 4.

[0094] Однако в некоторых вариантах осуществления компьютер 110 может создавать пакет 146 для инсталляции хеш-таблицы, который включает в себя команды на языке программирования аппаратного обеспечения, которые могут настраивать программируемую схему 162 для реализации блока 170 картирования и выравнивания в аппаратных цифровых логических схемах. Команды языка программирования аппаратного обеспечения могут иметь форму файла, такого как файл двоичного битового потока. Файл двоичного битового потока может быть сгенерирован перед его включением в пакет 146 для инсталляции хеш-таблицы путем компиляции кода языка программирования аппаратного обеспечения, такого как VHDL, Verilog или т.п., описывающего схему, которая должна быть реализована программируемой схемой 162. Команды языка программирования аппаратного обеспечения, входящие в пакет для инсталляции хеш-таблицы, при обработке программируемой схемой 162 могут привести к тому, что программируемая логическая схема запрограммирует динамически настраиваемые логические схемы программируемой логической схемы для реализации гибкого удлинения затравки путем выполнения хеш-запросов к хеш-таблице 140 в аппаратном обеспечении с использованием процессов, описанных со ссылкой на ФИГ. 3 и 4. Пакет 146 для инсталляции хеш-таблицы может также включать набор 132A таблиц удлинений затравки и команды по установке набора 132A таблиц удлинений затравки в память 180, доступную для программируемой схемы 162. Пакет 146 для инсталляции хеш-таблицы может также включать в себя хеш-таблицу 140 и команды по установке хеш-таблицы 140 в память 180, доступную для программируемой схемы 162. Программируемая схема 160 может быть запрограммирована на использование хеш-таблицы 140 в качестве компонента блока 170 картирования/выравнивания для выполнения картирования коротких затравок на эталонной последовательности, как более подробно описано в настоящем документе со ссылкой на ФИГ. 3. Компьютер 110 может передавать пакет для инсталляции хеш-таблицы на устройство 160, такое как настольный компьютер, портативный компьютер, планшетный компьютер, смартфон, облачный сервер, секвенатор или другое устройство, в котором находится программируемая схема 160, с помощью одной или более сетей, прямого соединения, такого как одна или более шин, кабеля USB или любой их комбинации. Устройство 160 может принимать пакет для инсталляции хеш-таблицы и программировать программируемую схему 162 на реализацию блока 170 картирования и выравнивания в аппаратных логических вентилях программируемой схемы 162 с помощью команд языка аппаратного программирования аппаратного обеспечения, входящих в пакет для инсталляции хеш-таблицы.

[0095] Таким образом, соответствующие пакеты 146 для инсталляции хеш-таблицы можно использовать различными способами для управления установкой, использованием и даже удалением хеш-таблицы 140 и таблицы удлинений затравки. Например, в некоторых вариантах осуществления каждая из хеш-таблиц 140 и наборов 132A таблиц удлинений затравки может храниться в виде файла на жестком диске или другом носителе данных, а затем, до обращения в оперативном режиме, каждая из них может быть загружена в обычную память, например в DRAM, где хранятся один или более компонентов или модулей для реализации оперативного гибкого удлинений затравки, как описано применительно к процессам, описанным в настоящем документе со ссылкой на ФИГ. 3 и 4. Однако в других вариантах осуществления хеш-таблица 140 или наборы 132A таблиц удлинений затравки могут храниться вместе или по отдельности, причем каждая в виде одного или более отдельных смежных участков в запоминающем устройстве или несмежных участков в запоминающем устройстве. Аналогичным образом хеш-таблица 140 или наборы 132A таблиц удлинений затравки могут быть сжаты или не сжаты, сохранены на общем или отдельных носителях данных и/или памяти, кэшированы или некэшированы, во время оперативного картирования или иным образом, если только имеется определенный путь и способ для того, чтобы блок 170 картирования и выравнивания в оперативном режиме обращался к выбранным частям как хеш-таблицы 140, так и набора 132A таблиц удлинений затравки. В других вариантах осуществления хеш-таблица 140 может быть полностью реализована в аппаратных логических схемах программируемой схемы 162, а наборы 132A таблиц удлинений затравки могут храниться в памяти 180, доступной для программируемой логической схемы 162, например в блоке памяти DRAM. В других вариантах осуществления хеш-таблица 140 может храниться в памяти 180, к которой может получать доступ программируемая логическая схема 162, например в памяти DRAM, а наборы 132A таблиц удлинений затравки могут быть полностью реализованы в аппаратных логических схемах программируемой схемы 162.

[0096] В некоторых вариантах осуществления компьютер 110 может также генерировать пакет для инсталляции, который включает компонент для построения хеш-таблицы и удлинений затравок, описанные в настоящем документе. Компьютер 110 может передавать пакет для инсталляции другому компьютеру по сети. Пакет для инсталляции можно использовать для инсталляции компонента для построения хеш-таблицы и удлинений затравки на другом компьютере или на отличающемся компьютере, чтобы сторона, которая принимает и устанавливает компонент для построения хеш-таблицы и удлинений затравки, могла создавать собственную хеш-таблицу и таблицу удлинений затравки на основе собственной выбранной эталонной последовательности и собственных выбранных настроек. Соответственно, получатель пакета для инсталляции компонента для построения хеш-таблицы и удлинений затравок может создавать собственную хеш-таблицу в любое время по выбранной последовательности, хранить ее на диске, загружать в память 180, доступную для программируемой схемы 162, и выполнять картирование и выравнивание с помощью программируемой схемы 162.

[0097] На ФИГ. 2 представлена блок-схема процесса 200 генерирования индекса хеш-таблицы, облегчающей гибкое удлинение затравки для геномного картирования на основе хеш-таблицы. По существу процесс 200 может включать получение с помощью компьютерной системы конкретной нуклеотидной затравки из эталонной последовательности, причем конкретная затравка представляет нуклеотидную последовательность, имеющую K нуклеотидов (210); определение с помощью компьютерной системы, что конкретная затравка имеет превышающее заданное число количество совпадений с позициями (220) эталонной последовательности; на основании определения того, что конкретная затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование с помощью компьютерной системы дерева удлинения затравки, имеющего множество узлов, причем каждый узел из множества узлов соответствует (i) удлиненной затравке, которая представляет собой удлинение конкретной затравки и имеет количество нуклеотидов K*, причем K* на один или более нуклеотидов больше K, и (ii) множеству позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой (230), а также для каждого узла из множества узлов: сохранение с помощью компьютерной системы информации об интервале в позиции хеш-таблицы, которая соответствует индексному ключу удлиненной затравки, причем информация об интервале ссылается на множество позиций в таблице удлинений затравки, включая данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, ассоциированной с узлом (240), с получением тем самым хеш-таблицы. Процесс 200 будет более подробно описан ниже как выполняемый компьютерной системой, такой как компьютер 110.

[0098] Более конкретно, компьютерная система может начинать выполнение процесса 200 с получения компьютерной системой конкретной нуклеотидной затравки из эталонной последовательности, причем конкретная затравка представляет собой последовательность нуклеотидов, имеющую K нуклеотидов (210). В некоторых вариантах осуществления получение конкретной затравки может включать в себя определение с помощью компьютерной системы позиции окна доступа к затравке в пределах эталонной последовательности. Затем компьютерная система может получать часть эталонной последовательности, идентифицированной окном доступа к затравке. Компьютерная система может включать в себя один или более компьютеров.

[0099] Компьютерная система может продолжать выполнение процесса 200 посредством определения с помощью компьютерной системы, имеет ли конкретная затравка количество совпадений с позициями (220) эталонной последовательности, превышающее заданное число. Если компьютерная система определяет, что конкретная затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности, компьютерная система может принимать решение не генерировать дерево удлинения затравки для этой конкретной затравки. Вместо этого компьютерная система может получать данные, описывающие каждую из позиций эталонной последовательности, которая совпадает со второй затравкой. Затем компьютерная система может хранить данные, описывающие позиции эталонной последовательности, которые совпадают с конкретной затравкой во второй позиции хеш-таблицы, соответствующей индексному ключу конкретной затравки.

[0100] В альтернативном варианте осуществления, если компьютерная система определяет, что конкретная затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, компьютерная система может генерировать дерево удлинения затравки, имеющее множество узлов (230). Каждый узел из множества узлов может включать данные, представляющие (i) удлиненную затравку, которая представляет собой удлинение конкретной затравки и имеет количество нуклеотидов K*, причем K* на один или более нуклеотидов больше, чем K, и (ii) множество позиций в таблице удлинений затравки, включая данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой. В некоторых вариантах осуществления множество позиций может включать непрерывный интервал в таблице удлинений затравки из позиций эталонной последовательности, которые совпадают с удлиненной затравкой, ассоциированной с узлом.

[0101] Компьютерная система может продолжать выполнение процесса 200 путем хранения информации об интервале в хеш-позициях хеш-таблицы для каждого узла дерева удлинения затравки. В некоторых вариантах осуществления в компьютерной системе может храниться информация об интервале для каждого узла дерева удлинения затравки в хеш-позиции хеш-таблицы, соответствующей индексному ключу для удлиненной затравки, и, следовательно, генерируется хеш-таблица (240). Информация об интервале может включать ссылки на множество позиций таблицы удлинений затравки, включая данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, ассоциированной с узлом. В некоторых вариантах осуществления множество позиций таблицы удлинений затравки, описанное в информации об интервале, может включать непрерывный интервал позиций в таблице удлинений затравки, включая данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой.

Оперативное гибкое удлинение затравок с использованием геномного картирования на основе хеш-таблицы

[0102] На ФИГ. 3 представлена контекстная схема исполнительной системы 300 для оперативного выполнения гибкого удлинения затравки при геномном картировании на основе хеш-таблицы. Исполнительная система 300 включает в себя программируемую логическую схему 162, блок 170 картирования и выравнивания, хеш-таблицу 140, память 18 и множество таблиц удлинений затравки, такие как таблица 132 удлинений затравки, хранящихся в памяти 180. В примере на ФИГ. 3 представлен блок 170 картирования и выравнивания, а также хеш-таблица 140, реализованная в аппаратном обеспечении с использованием аппаратных логических схем программируемого логического блока 162, причем настоящее описание этим вариантом не ограничивается. Вместо этого блок 170 картирования и выравнивания может представлять собой программное приложение, реализованное с использованием программных команд, исполняемых одним или более ЦП, ГП или их комбинацией, получающим доступ к хеш-таблице 140, хранящейся в блоке памяти.

[0103] Выполнение с помощью системы 300 оперативного гибкого удлинения затравки для геномного картирования на основе хеш-таблицы может быть запущено блоком 170 картирования и выравнивания с доступа к текущему чтению 305. Текущее чтение 305 может быть получено с помощью секвенатора нуклеиновых кислот, который провел первичный анализ биологического образца. Первичный анализ может включать в себя прием секвенатором нуклеиновых кислот биологического образца, такого как образец крови, образец ткани или мокроты, и генерирование выходных данных, таких как одно или более чтений 305, которые представляют порядок нуклеотидов в нуклеотидных последовательностях в принятом биологическом образце. В некоторых вариантах осуществления биологический образец может включать образец ДНК, а секвенатор нуклеиновых кислот может включать секвенатор ДНК. В таких вариантах осуществления порядок секвенированных нуклеотидов в чтении 305, полученном секвенатором нуклеиновых кислот, может включать один или более из гуанина (G), цитозина (C), аденина (A) и тимина (T) в любой комбинации. В других вариантах осуществления секвенатор нуклеиновых кислот может включать секвенатор РНК, а биологический образец может включать образец РНК. В таких вариантах осуществления порядок секвенированных нуклеотидов в чтении, полученном секвенатором нуклеиновых кислот, может включать один или более из G, C, A и урацила (U) в любой комбинации. Таким образом, в примере, показанном на ФИГ. 3 описана обработка чтения, состоящего из G, C, A и T, полученного секвенатором ДНК на основе образца ДНК, причем настоящее описание не ограничивается этим. Вместо этого в других вариантах осуществления процесс может обрабатывать чтения, состоящие из C, G, A и U, которые получены секвенатором РНК на основе образца РНК.

[0104] Как правило, блок 170 картирования и выравнивания может быть выполнен не зависящим от типа чтения, которое он принимает, картирует и выравнивает. Например, в некоторых вариантах осуществления для представления T и U можно использовать один и тот же двоичный код. Чтение, принятое блоком 170 картирования и выравнивания, может включать ДНК, кДНК и/или РНК, и в качестве эталона можно использовать ДНК, кДНК и/или РНК. В таких вариантах осуществления основания T и/или U в чтении могут использовать один и тот же двоичный код так, что T и/или U в чтении совпадают с T и/или U в эталоне.

[0105] В некоторых вариантах осуществления секвенатор нуклеиновых кислот может включать секвенатор следующего поколения (NGS), который выполнен с возможностью генерирования чтений последовательностей, например чтения 305, для данного образца таким образом, чтобы обеспечивать сверхвысокую пропускную способность, масштабируемость и скорость за счет использования технологии массового параллельного секвенирования. NGS позволяют быстро секвенировать целые геномы, обеспечивают возможность глубокого изучения секвенированных целевых областей, использования секвенирования РНК (RNA-Seq) для обнаружения новых вариантов РНК и сайтов сплайсинга или количественно определять мРНК для анализа генной экспрессии, проводить анализ эпигенетических факторов, таких как метилирование ДНК в масштабах генома и ДНК-белковые взаимодействия, секвенирование образцов опухолей для исследования редких соматических вариантов и субклонов опухоли, а также изучение разнообразия микроорганизмов у людей или в окружающей среде.

[0106] К чтениям последовательностей, таким как чтение 305, полученным секвенатором нуклеиновых кислот, может иметь доступ блок вторичного анализа, такой как блок 170 картирования и выравнивания, и может проводить их обработку. В некоторых вариантах осуществления блок вторичного анализа, такой как блок 170 картирования и выравнивания, может быть реализован в виде аппаратного обеспечения, такого как цифровые логические схемы, с использованием программируемой схемы 162, такой как программируемая пользователем интегральная схема (FPGA) или специализированная интегральная схема (ASIC). В других вариантах осуществления блок вторичного анализа, такой как блок 170 картирования и выравнивания, может быть реализован с использованием одного или более ЦП, ГП или их комбинации для осуществления функциональных возможностей блока 170 картирования и выравнивания. Хотя хеш-таблица 140 может быть реализована в аппаратных логических схемах программируемой схемы 162 в некоторых вариантах осуществления, например когда блок 170 картирования и выравнивания реализован с использованием программируемой схемы 162, настоящее описание этим не ограничивается. Вместо этого хеш-таблица 140 может храниться в запоминающем устройстве с доступом по мере необходимости со стороны (i) ЦП, ГП или их комбинации, выполняющих программные команды, реализующие функциональные возможности блока 170 картирования и выравнивания, или (ii) блока 170 картирования и выравнивания, который был реализован в аппаратных цифровых логических схемах.

[0107] В некоторых вариантах осуществления программируемая схема 162 может быть интегрирована с секвенатором нуклеиновых кислот, сгенерировавшим чтение 305. В таких вариантах осуществления, например, программируемая схема 162 может быть размещена на плате расширения, такой как плата расширения на шине соединения периферийных устройств (PCI), установленной в секвенатор нуклеиновых кислот. В других вариантах осуществления, например, каждая программируемая схема 162 может быть частью другого компьютера, который отличается от секвенатора нуклеиновых кислот и напрямую соединен с секвенатором нуклеиновых кислот при помощи кабеля Ethernet, кабеля USB, кабеля USB-C или т.п. Например, в других вариантах осуществления программируемая схема 162 может быть интегрирована в облачный сервер с возможностью удаленного доступа для секвенатора нуклеиновых кислот, генерирующего чтение 305, с помощью одной или более проводных или беспроводных сетей, таких как локальная сеть (LAN), глобальная сеть (WAN), сотовая сеть, Интернет или их комбинации.

[0108] Блок 170 картирования и выравнивания может принимать первый хеш-запрос 310, который включает начальную затравку GTTTA 310a. В некоторых вариантах осуществления хеш-запрос может состоять только из затравки из чтения образца, такого как текущее чтение 305, используемой в качестве входных данных для хеш-таблицы 140. В других вариантах осуществления к затравке из чтения образца можно добавлять дополнительные данные, метаданные или т.п. для перевода чтения образца в формат, который можно использовать для поиска в хеш-таблице 140.

[0109] В примере на ФИГ. 3 начальная затравка GTTTA 310a, включенная в хеш-запрос 310, получена из первой части текущего чтения ACGTTTAGC 305, и идентифицирована с помощью окна 305a доступа к затравке. Блок 170 картирования и выравнивания может выполнять хеш-запрос 310 с использованием хеш-таблицы 140, чтобы картировать начальную короткую затравку 310a с хеш-позицией 144 с помощью хеш-функции 143. В примере на ФИГ. 3 при выполнении хеш-запроса 310 определяют, что затравка GTTTA 310a соответствует индексному ключу GTTTA 142-2 хеша, сопоставляемому с хеш-позицией 144-y хеш-функцией 143.

[0110] Блок 170 картирования и выравнивания может генерировать ответ 310b на хеш-запрос 310 с использованием хеш-таблицы 140. Ответ 310b может включать содержимое хеш-позиции 144-y, охватываемой затравкой 310a, входящей в хеш-запрос 310. Блок 170 картирования и выравнивания оценивает ответ 310b на хеш-запрос 310 и определяет, включены ли в содержимое набор совпадающих позиций эталонной последовательности, запись об удлинении, запись об интервале или их комбинация. Если ответ 310b включает только набор совпадающих позиций эталонной последовательности без записи об удлинении или записи об интервале, блок 170 картирования и выравнивания может хранить набор совпадающих позиций эталонной последовательности в наборе 352 совпадений с затравкой вместе с метаданными, которые ассоциируют совпадающие позиции эталонной последовательности с затравкой принятого запроса. В альтернативном варианте осуществления, если блок 170 картирования и выравнивания определяет, что ответ включает запись об интервале и/или запись об удлинении, блок 170 картирования и выравнивания должен определять 320, нужно ли использовать совпадающие с эталоном затравки, идентифицированные записью об интервале, или продолжать удлинение затравки из запроса.

[0111] В примере на ФИГ. 3 оценка ответа 310b показывает, что (i) ответ не включает набор совпадающих позиций эталонной последовательности и (ii) что ответ 310b включает запись 153a об удлинении и запись 153b об интервале. На основании ответа 310b блок 170 картирования и выравнивания может определять 320, должен ли быть доступ к соответствующим совпадающим позициям эталонной последовательности, идентифицированным записью 153b об интервале. В некоторых вариантах осуществления блок 170 картирования и выравнивания не будет получать доступ к совпадающим позициям эталонной последовательности, идентифицированным записью об интервале, такой как запись 153b об интервале, если ответ, такой как 310b, на хеш-запрос 310, включает запись 153а об удлинении.

[0112] Однако в других вариантах осуществления блок 170 картирования и выравнивания может быть выполнен с возможностью оценки числа совпадающих позиций эталонной последовательности, идентифицированных записью 153b об интервале перед удлинением затравки 310a с использованием записи 153b об удлинении. В таких вариантах осуществления, если число совпадающих позиций эталонной последовательности оказывается меньше заданного порогового значения, блок 170 картирования и выравнивания может выводить 310d совпадающие позиции эталонной последовательности интервала А, идентифицированного записью об интервале. Вывод совпадающих позиций эталонной последовательности может включать в себя доступ блока 170 картирования и выравнивания к совпадающим позициям эталонной последовательности, хранящимся в интервале A таблицы 132 удлинений затравки, в памяти 180, и хранение доступных совпадающих позиций эталонной последовательности в хранилище 352 набора совпадений с затравкой. После сохранения доступных совпадающих позиций эталонной последовательности в наборе 352 совпадений с затравкой процесс, описанный на ФИГ. 3, может заканчиваться без дальнейшего удлинения затравки 310a. Затем окно 305a доступа к затравке можно передвигать вперед на один или более нуклеотидов по текущему чтению 305. После перемещения окна 305a доступа к затравке процесс, описанный со ссылкой на ФИГ. 3, может начинаться снова и итеративно продолжаться до тех пор, пока не будет опрошено все текущее чтение 305. С другой стороны, в данном альтернативном варианте осуществления, если было определено, что число совпадающих позиций эталонной последовательности не опускается ниже заданного порогового значения, затравка 310a может быть удлинена с использованием записи 152a об удлинении.

[0113] Возвращаясь к примеру, показанному на ФИГ. 3, блок 170 картирования и выравнивания не применяет указанные выше пороговые значения к совпадениям, идентифицированным посредством записи 153b об интервале. Вместо этого блок 170 картирования и выравнивания принимает решение 320 не использовать совпадающие позиции эталонной последовательности, идентифицированные записью 153b об интервале, поскольку вывод 310b включает в себя запись 153a об удлинении. Соответственно, в этом сценарии блок 170 картирования и выравнивания принимает решение удлинить затравку 310a.

[0114] Перед переходом к выполнению последующего запроса на основе удлиненной затравки, блок картирования и выравнивания может хранить информацию, описывающую интервал A 310c, в хранилище 350 «наилучшего интервала». Интервал A можно считать «наилучшим интервалом» для совпадающих позиций эталонной последовательности в таблице 132 удлинений затравки для затравки 310a, поскольку другие интервалы еще не идентифицированы и не оценены на данном этапе процесса. Однако в последующих итерациях процесса, показанного на ФИГ. 3, можно эвристически оценивать каждый последующий интервал и определять, лучше ли интервал по сравнению с существующим интервалом, хранящимся в хранилище наилучшего интервала для первоначальной затравки 310a или ее удлиненных затравок. Благодаря хранению информации, описывающей интервал A 310c, в хранилище 340 наилучшего интервала можно пересматривать совпадающие позиции эталонной последовательности интервала A, если при удлинении первоначальной затравки 310a происходит сбой в картировании, например проблема некартированного чтения или проблема высокодостоверного неправильного картирования. Информация, описывающая интервал A 310c, может включать данные, описывающие начальную и конечную позицию непрерывного списка позиций эталонной последовательности, которые совпадают с первоначальной затравкой. В некоторых вариантах осуществления информация, описывающая интервал A 310c, может также включать данные, идентифицирующие затравку, с которой совпадают позиции эталонной последовательности, идентифицированные совпадением с интервалом A.

[0115] За выполнением гибкого удлинения затравки блоком 170 картирования и выравнивания может последовать генерирование блоком 170 картирования и выравнивания первой удлиненной затравки 312a, которая представляет собой удлинение первоначальной затравки 310a с использованием записи 153a об удлинении. В примере на ФИГ. 3 в запись об удлинении 153a может быть включена одна или более команд, посредством которых блок 170 картирования и выравнивания симметрично удлиняет исходную затравку 310a на два основания или нуклеотида. В примере на ФИГ. 3 при симметричном удлинении начальной затравки GTTTA 310a на два основания или нуклеотида формируется удлиненная затравка CGTTTAG 312a для чтения 305. В некоторых вариантах осуществления дополнительные нуклеотиды C и G, используемые для удлинения начальной затравки 310a, могут быть получены из следующих нуклеотидов чтения 305, находящихся с противоположных сторон от начальной затравки 310a, обозначенной окном 305a доступа к затравке.

[0116] Хотя с каждой стороны окна доступа к затравке имеется дополнительная затравка, упрощающая удлинение этой затравки, в других вариантах осуществления, например, когда окно доступа к затравке находится в начале чтения 305, при удлинении начальная затравка может выходить за границы чтения 305. В таких вариантах осуществления удлинение затравки может оказаться неудачным, и процесс картирования начальной затравки по совпадающим позициям эталонной последовательности с использованием хеш-таблицы 140 может прерываться без добавления каких-либо совпадающих позиций эталонной последовательности к набору 352 совпадений с затравкой при цикле запроса, который начался с начальной затравки. Однако в таких вариантах осуществления окно 305a доступа к затравке можно смещать на один или более нуклеотидов вперед вдоль чтения 305, и можно получать следующую затравку чтения 305, идентифицируемую перемещенным окном доступа к затравке, для применения в качестве начальной затравки для нового цикла запроса с использованием хеш-таблицы 140. Выполнение нового цикла запроса для следующей затравки и каждой последующей затравки, пока не будут обработаны все затравки 305, можно использовать для обновления данных в хранилище 350 наилучшего интервала и/или для хранения одного или более наборов совпадающих позиций эталонной последовательности в хранилище 352 для набора совпадений с затравкой, которые можно оценивать для идентификации оптимального набора совпадающих позиций эталонной последовательности для данного чтения 305, как описано со ссылкой на ФИГ. 5, несмотря на неудачное удлинение затравки, таким образом, решаются проблемы некартированных чтений, которые могут быть свойственны традиционным способам.

[0117] Сходные сбои при удлинении затравок могут происходить по тем же причинам при продвижения окна 305а доступа к затравке к противоположным концам чтения 305. В настоящем описании аналогичным образом решаются проблемы этих неудачных удлинений затравки путем оценки хранилища 250 наилучшего интервала, наборов 353 совпадений с затравкой из предыдущих итераций хеш-запросов для данного чтения, как описано со ссылкой на ФИГ. 5, или и того и другого.

[0118] Возвращаясь к примеру, показанному на ФИГ. 3, блок 170 картирования и выравнивания может генерировать последующий хеш-запрос 312, который включает первую удлиненную затравку 312a. Блок 170 картирования и выравнивания может получать первую удлиненную затравку 312a из хеш-запроса 312 и использовать хеш-таблицу для картирования первой удлиненной короткой затравки 312a по хеш-позиции 144 с помощью хеш-функции 143. В некоторых вариантах осуществления создание хеш-запроса 312 с использованием первой удлиненной затравки 312a может включать в себя передачу первой удлиненной затравки 312a блоку 170 картирования и выравнивания в качестве входных данных для картирования затравок с использованием хеш-таблицы 140 без создания запроса. В примере на ФИГ. 3 при выполнении хеш-запроса 312 определяют, что затравка CGTTTAG 312a соответствует индексному ключу CGTTTAG 142-x хеша, сопоставляемому с хеш-позицией 144-3 хеш-функцией 143.

[0119] Блок 170 картирования и выравнивания может генерировать ответ 312b на хеш-запрос 312 с использованием хеш-таблицы 140. Ответ 312b может включать содержимое хеш-позиции 144-3, охватываемой затравкой 312a, входящей в хеш-запрос 312. Блок 170 картирования и выравнивания может оценивать ответ 312b на хеш-запрос 312 и определять, что ответ 312b (i) не включает набор совпадающих позиций эталонной последовательности и (ii) включает запись 152a об удлинении и запись 152b об интервале. На основании ответа 312b блок 170 картирования и выравнивания может определять 330, должен ли быть доступ к соответствующим совпадающим позициям эталонной последовательности, идентифицированным записью 152b об интервале. В некоторых вариантах осуществления блок 170 картирования и выравнивания не будет получать доступ к совпадающим позициям эталонной последовательности, идентифицированным записью об интервале, такой как запись 152b об интервале, если ответ, такой как 312b, на хеш-запрос 312, включает запись 152а об удлинении.

[0120] Однако в других вариантах осуществления блок 170 картирования и выравнивания может быть выполнен с возможностью оценки числа совпадающих позиций эталонной последовательности, идентифицированных записью 152b об интервале перед удлинением затравки 312a с использованием записи 152b об удлинении. В таких вариантах осуществления, если число совпадающих позиций эталонной последовательности, идентифицированное записью 152b об интервале, оказывается меньше заданного порогового значения, блок 170 картирования и выравнивания может выводить 312d совпадающие позиции эталонной последовательности интервала B, идентифицированного записью об интервале 152b. Вывод совпадающих позиций эталонной последовательности может включать в себя доступ к совпадающим позициям эталонной последовательности, хранящимся в интервале B таблицы 132 удлинений затравки, с помощью блока 170 картирования и выравнивания в памяти 180, и хранение доступных совпадающих позиций эталонной последовательности в хранилище 352 набора совпадений с затравкой. После сохранения доступных совпадающих позиций эталонной последовательности в хранилище 352 набора совпадений с затравкой процесс, описанный на ФИГ. 3, может заканчиваться без дальнейшего удлинения затравки 312a. Затем окно 305a доступа к затравке можно передвигать на один или более нуклеотидов по текущему чтению 305. После перемещения окна 305a доступа к затравке процесс, описанный со ссылкой на ФИГ. 3, может начинаться снова и итеративно продолжаться до тех пор, пока не будет опрошено все текущее чтение 305. С другой стороны, в данном альтернативном варианте осуществления, если было определено, что число совпадающих позиций эталонной последовательности не опускается ниже заданного порогового значения, затравка 312a может быть удлинена с использованием записи 152a об удлинении.

[0121] Возвращаясь к примеру, показанному на ФИГ. 3, блок 170 картирования и выравнивания не применяет указанное выше пороговое значение к совпадениям, идентифицированным посредством записи 152b об интервале. Вместо этого блок 170 картирования и выравнивания принимает решение 330 не использовать совпадающие позиции эталонной последовательности, идентифицированные записью 152b об интервале, поскольку вывод 312b включает в себя запись 152a об удлинении. Соответственно, блок 170 картирования и выравнивания принимает решение удлинить затравку 312a.

[0122] Перед переходом к выполнению последующего запроса на основе удлиненной затравки, блок картирования и выравнивания может принимать решение о хранении информации, описывающей интервал B 312c в хранилище 350 наилучшего интервала в качестве «наилучшего интервала». Решение о хранении информации, описывающей интервал B 312c как «наилучший интервал», включает эвристическое определение, лучше ли интервал B, чем интервал, в настоящий момент хранящийся в хранилище 352 наилучшего интервала для предыдущей итерации первой удлиненной затравки, который в этом примере представляет собой интервал A. В одном варианте осуществления наилучший интервал из множества интервалов можно определять путем оценки количества целевых совпадений, полученного для каждого интервала. В таком варианте осуществления «наилучший интервал» может быть выбран в соответствии с правилом многокомпонентности. В качестве примера блок 170 картирования и выравнивания может назначать первый приоритет интервалу, который содержит по меньшей мере заданное число совпадающих позиций эталонной последовательности, на которое может ссылаться порог, такой как число совпадений «ориентир-для-интервала»(32). Однако, если у всех интервалов число совпадений меньше ориентира-для-интервала(32), интервал с большим количеством совпадений хранится в качестве наилучшего интервала. Кроме того, блок 170 картирования и выравнивания может присваивать второй приоритет интервалу, ассоциированному с более длинной затравкой, поскольку такие интервалы могут быть предпочтительными. Более того, если блок 170 картирования и выравнивания определяет, что по меньшей мере один интервал имеет число совпадений по меньшей мере равное ориентиру-для-интервала(32), среди всех интервалов, удовлетворяющих требованию о по меньшей мере равенстве ориентиру-для-интервала(32), в качестве наилучшего интервала выбирают интервал, ассоциированный с наиболее длинной удлиненной затравкой. Хотя данный пример относится к пороговому значению ориентир-для-интервала(32),составляющему 32 совпадения, настоящее описание необязательно должно иметь такое ограничение. Вместо этого для реализации этого эвристического правила многокомпонентности, значению ориентир-для-интервала() может быть присвоено любое число совпадающих позиций эталонной последовательности.

[0123] В примере на ФИГ. 3 интервал A, ранее хранящийся в качестве наилучшего интервала в хранилище 350 наилучшего интервала, идентифицирует шесть совпадающих позиций эталонной последовательности от 132-1 до 132-6, а интервал B идентифицирует три совпадающих позиции эталонной последовательности от 132-4 до 132-6. С помощью примера порогового значения ориентир-для-интервала(10) в десять совпадений блок 170 картирования и выравнивания может применять эвристическое правило многокомпонентности и определять, что ни один интервал не удовлетворяет порогу ориентир-для-интервала(10). Таким образом, в соответствии с правилом многокомпонентности блок 170 картирования и выравнивания может выбирать интервал A в качестве наилучшего интервала, поскольку интервал A имеет больше всего совпадений, т.е. шесть, из интервала A и интервала B. На основании применения этого примера эвристического правила многокомпонентности, информация, описывающая интервал B 321c, может быть отброшена, а интервал A все еще считается наилучшим интервалом. Однако в других примерах, в которых применяют другое эвристическое правило, которое не обязательно должно представлять собой эвристическое правило многокомпонентности, в качестве наилучшего интервала может быть выбран интервал B и сохранен в хранилище 350 наилучшего интервала вместо интервала A. Такие результаты в конечном итоге могут быть оставлены для конкретных конструктивных конфигураций, например, с установкой порога ориентир-для-интервала(), разработкой одного или более эвристических правил или т.п.

[0124] В примере на ФИГ. 3 вышеупомянутое эвристическое правило используют для сравнения интервала A, ранее хранящегося в хранилище 350 наилучшего интервала, и интервала B, который входит в ответ 312b, на запрос 312. Тем не менее настоящее описание не обязательно ограничено таким образом. Например, в некоторых вариантах осуществления ответ на хеш-запрос может включать множество записей об интервалах, которые хранились в хеш-позиции 144, охватываемой конкретной затравкой хеш-запроса. В таких вариантах осуществления блок 170 картирования и выравнивания может применять вышеупомянутые эвристические правила для принятия решения о том, к какой из множества записей об интервалах следует обращаться. Аналогичным образом блок 170 картирования и выравнивания может также использовать такие эвристические правила для определения наилучшего интервала для хранения в хранилище 450 наилучшего интервала из всех записей об интервалах, полученных в ответ на запрос. В качестве другого примера блок 170 картирования и выравнивания может также использовать такие эвристические правила для определения наилучшего интервала для хранения в хранилище 450 наилучших интервалов среди всех записей об интервалах, полученных в ответ на запрос, и другого интервала, ранее хранящегося в хранилище 350 наилучшего интервала в предыдущей итерации затравки, используемой в запросе, вернувшем множество интервалов.

[0125] В некоторых вариантах осуществления система 300 может способствовать хранению более одного наилучшего интервала в хранилище 350 наилучших интервалов. Например, в некоторых вариантах осуществления можно отслеживать до 2 наилучших интервалов. В некоторых вариантах осуществления можно отслеживать до N наилучших интервалов. В таких вариантах осуществления, если хранятся N > 1 лучших интервалов, критерии определения сохранения интервалов могут включать оценку взаимоотношений между потенциальными интервалами и/или связанными с ними удлиненными затравками или среди них, например требование, чтобы N наилучших интервалов были ассоциированы с удлиненными затравками, которые не накладываются друг на друга в пределах чтения.

[0126] За выполнением гибкого удлинения затравки блоком 170 картирования и выравнивания может последовать генерирование блоком 170 картирования и выравнивания второй удлиненной затравки 314a, которая представляет собой удлинение первой удлиненной затравки 312a с использованием записи 152a об удлинении. В примере на ФИГ. 3 в запись об удлинении 152a может быть включена одна или более команд, посредством которых блок 170 картирования и выравнивания симметрично удлиняет первую удлиненную затравку 312a на два основания или нуклеотида. В примере на ФИГ. 3 симметричное удлинение первой удлиненной затравки CGTTTAG 312a двумя основаниями или нуклеотидами приводит к получению второй удлиненной затравки ACGTTTAGC 314a для чтения 305. В некоторых вариантах осуществления дополнительные нуклеотиды A и C, используемые для удлинения первой удлиненной затравки 312a, могут быть получены из следующих нуклеотидов чтения 305, находящихся с противоположных сторон от первой удлиненной затравки CGTTTAG 312a.

[0127] Возвращаясь к примеру, показанному на ФИГ. 3, блок 170 картирования и выравнивания может генерировать последующий хеш-запрос 314, который включает вторую удлиненную затравку 314a. Блок 170 картирования и выравнивания может получать вторую удлиненную затравку 314a из хеш-запроса 314 и использовать хеш-таблицу для картирования второй удлиненной короткой затравки 314a по хеш-позиции 144 с помощью хеш-функции 143. В некоторых вариантах осуществления создание хеш-запроса 314 с использованием второй удлиненной затравки 314a может включать в себя передачу второй удлиненной затравки 314a блоку 170 картирования и выравнивания в качестве входных данных для картирования затравок с использованием хеш-таблицы 140 без создания запроса. В примере на ФИГ. 3 при выполнении хеш-запроса 314 определяют, что затравка ACGTTTAGC 314a соответствует индексному ключу ACGTTTAGC 142-1 хеша, сопоставляемому с хеш-позицией 144-2 хеш-функцией 143.

[0128] Блок 170 картирования и выравнивания может генерировать ответ 314b на хеш-запрос 314 с использованием хеш-таблицы 140. Ответ 314b может включать содержимое хеш-позиции 144-2, охватываемой второй удлиненной затравкой 314a, входящей в хеш-запрос 314. Блок 170 картирования и выравнивания оценивает ответ 314b на хеш-запрос 314 и определяет, что ответ 314b (i) включает набор совпадающих позиций 155 эталонной последовательности, (ii) не включает запись об удлинении и (iii) не включает запись об интервале. На основании ответа 314b блок 170 картирования и выравнивания может решать, что совпадающие позиции 155 эталонной последовательности должны храниться в хранилище 352 набора совпадений с затравкой.

[0129] Поскольку ответ 314b не включает запись об удлинении, процесс оперативного гибкого удлинения затравки GTTTA 310a чтения 305 завершается. Окно 305a доступа к затравке можно продолжать продвигать на один или более нуклеотидов вдоль чтения 305 до выполнения каждого процесса, описанного со ссылкой на ФИГ. 3 для каждой из соответствующих затравок чтения 305. Этот процесс также описан со ссылкой на блок-схему, изображенную на ФИГ. 4. Как описано выше, когда окно 305a доступа к затравке доходит до конца чтения 305, попытки ввести удлиненную затравку в блок 170 картирования и выравнивания могут оказаться неудачными, вследствие чего возникает потенциальная проблема некартированных чтений. Однако в настоящем описании можно использовать один или более интервалов, хранящихся в хранилище наилучших интервалов, одно или более чтений, хранящихся в наборе 352 совпадений с затравкой, или их комбинацию для идентификации набора совпадающих позиций эталонной последовательности для чтения 305, как описано со ссылкой на по меньшей мере ФИГ. 5.

[0130] На ФИГ. 4 представлена блок-схема процесса 400 для выполнения оперативного гибкого удлинения затравки для геномного картирования на основе хеш-таблицы. Процесс 400 будет разъяснен ниже как выполняемый компьютерной системой из одного или более компьютеров. Один или более компьютеров могут включать в себя, например, блок 170 картирования и выравнивания. Для целей настоящего описания один или более компьютеров могут включать в себя ЦП или ГП, который выполнен с возможностью получения и выполнения программных команд для реализации конкретной запрограммированной функциональной возможности, описанной в программных командах. В альтернативном или дополнительном варианте осуществления один или более компьютеров могут включать программируемую схему, выполненную таким образом, что аппаратные цифровые логические схемы программируемой схемы выполнены с возможностью реализации конкретной запрограммированной функциональности в аппаратном обеспечении.

[0131] Компьютерная система может запускать выполнение процесса 400 путем выполнения запроса к хеш-таблице 405. Запрос может включать затравку из нуклеотидов. Затравка из нуклеотидов может включать подгруппу нуклеотидов, полученных из чтения. Чтение может включать набор нуклеотидов, сгенерированный секвенатором нуклеиновых кислот на основе биологического образца, который был введен в секвенатор нуклеиновых кислот. Биологический образец может включать, например, образец крови, образец ткани, мокроту или т.п.

[0132] Например, чтение, созданное секвенатором нуклеиновых кислот на основе биологического образца, может включать последовательность нуклеотидов, такую как ACGTTTAGC. Данный пример включает чтение из 9 нуклеотидов. Однако чтение из 9 нуклеотидов используют только в качестве примера. Вместо ограничения 9 нуклеотидами, чтения, приводимые в настоящем описании, могут иметь любое количество нуклеотидов, включая, без ограничений, 5 оснований или нуклеотидов, 10 оснований или нуклеотидов, 12 оснований или нуклеотидов, 15 оснований или нуклеотидов, 18 оснований или нуклеотидов, 21 основание или нуклеотид, 25 оснований или нуклеотидов, 35 оснований или нуклеотидов, 50 оснований или нуклеотидов, 100 оснований нуклеотидов, 150 оснований или нуклеотидов, 1000 оснований или нуклеотидов, 1 000 000 оснований или нуклеотидов или даже большее количество оснований или нуклеотидов. Затравка из запроса может включать часть чтения, например GTTTA. В затравке, полученной из чтения для использования в первом хеш-запросе во время первой итерации процесса 400, может быть любое количество K, причем K меньше числа оснований или нуклеотидов в чтении. В некоторых вариантах осуществления K может быть существенно меньше числа нуклеотидов в чтении, например 1/100 длины чтения, 1/10 длины чтения, 1/5 длины чтения или т.п.

[0133] Компьютерная система может выполнять запрос, включающий затравку, путем получения затравки и сравнения затравки с хеш-ключами хеш-таблицы. Хеш-ключи могут соответствовать каждой затравке эталонной последовательности, обратному комплементу каждой затравки эталонной последовательности, каждой удлиненной затравке эталонной последовательности и обратному комплементу каждой удлиненной затравки эталонной последовательности. Эталонная последовательность может включать, например, эталонный геном или его участок для биологического вида, такого как человек или другое животное. При выявлении хеш-ключа, который соответствует затравке из запроса, компьютерная система может использовать хеш-функцию для соотнесения хеш-ключа с одной или более хеш-позициями. В некоторых аспектах настоящего описания в одной или более хеш-позициях могут храниться (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более позиций эталонной последовательности. Компьютерная система может формировать ответ на запрос, включающий содержимое одной или более хеш-позиций, охватываемых затравкой из запроса.

[0134] Компьютерная система может продолжать выполнение процесса 400 путем получения ответа на выполненный запрос, который включает в себя информацию, хранящуюся в одной или более позициях хеш-таблицы, которые определены как охватываемые запросом (410). Считается, что одна или более позиций хеш-таблицы входит в запрос, если установлено, что затравка из запроса совпадает с хеш-ключом, который сопоставлен с одной или более позициями с использованием хеш-функции.

[0135] Компьютерная система может продолжать выполнение процесса 400 и определять, включены ли в ответ на выполненный запрос (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций (415) эталонной последовательности. Определение с помощью компьютерной системы, включены ли в ответ на выполненный запрос (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций (415) эталонной последовательности, может включать в себя обработку принятого ответа и анализ обработанных данных ответа. Компьютерная система на основе обработанных данных может определять, представляют ли собой обработанные данные (i) запись об удлинении, (ii) запись об интервале или (iii) одну или более совпадающих позиций эталонной последовательности. В других вариантах осуществления ответ на выполненный запрос может включать в себя один или более флагов данных, которые указывают, включены ли в ответ (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности.

[0136] В некоторых случаях компьютерная система может продолжать выполнение процесса 400 путем определения на стадии 415, что в ответ не включены запись об удлинении, запись об интервале или одна или более совпадающих позиций эталонной последовательности. Если компьютерная система определяет, что в ответ не включены (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности, процесс заканчивается на стадии 420 без добавления каких-либо совпадающих позиций эталонной последовательности к набору совпадений с затравкой из запроса. Например, в полученный ответ на запрос, включающий затравку, могут не быть включены (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности, если затравка представляет собой удлиненную затравку и присутствует ошибка удлинения затравки. Такая ошибка удлинения затравки может возникать, например, при попытке компьютерной системы удлинить затравку за рамки чтения, из которого была получена затравка.

[0137] В альтернативном варианте осуществления в других случаях компьютерная система может продолжать выполнение процесса 400 и определять на стадии 415, что в ответ на выполненный запрос включены (i) запись об удлинении, (ii) запись об интервале или (iii) обе эти записи. В таких случаях компьютерная система может продолжать выполнение процесса 400 и решать, должен ли быть доступ к таблице удлинений для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается запись об интервале (430).

[0138] В некоторых случаях компьютерная система может продолжать выполнение процесса 400 и решать, что должен быть доступ к таблице удлинений затравки для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается запись об интервале. Например, в некоторых вариантах осуществления компьютерная система может быть выполнена с возможностью доступа к таблице удлинений затравки для получения одной или более совпадающих позиций эталонной последовательности, идентифицированных записью об интервале, если число совпадающих позиций эталонной последовательности оказывается ниже заданного порогового значения. В альтернативном или дополнительном варианте осуществления компьютерная система может быть выполнена с возможностью доступа к таблице удлинений затравки для получения одной или более совпадающих позиций эталонной последовательности, идентифицированных записью об интервале, если в ответ на выполненный запрос также включена запись типа «ОСТАНОВКА», хранящаяся в хеш-позиции, охваченной затравкой из хеш-запроса. Запись «ОСТАНОВКА» может давать компьютерной системе команду не выполнять дальнейшее удлинение затравки, входящей в запрос, и обратиться к одной или более совпадающим позициям эталонной последовательности, идентифицированным записью об интервале, предпочтительно, например, если число совпадающих позиций эталонной последовательности оказывается ниже заданного порогового значения.

[0139] В таких случаях, когда компьютерная система определяет на стадии 430, что необходим доступ к таблице удлинений затравки, компьютерная система может продолжать выполнение процесса 400 и получать доступ к таблице удлинений затравки для получения одной или более позиций эталонной последовательности в таблице удлинений затравки (450). Компьютерная система может идентифицировать конкретный набор из одной или более совпадающих позиций эталонной последовательности, предназначенный для получения, по таблице удлинений затравки с применением записи об интервале. Запись об интервале может включать информацию, которая ссылается на множество позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с затравкой из запроса. В некоторых вариантах осуществления информация, которая ссылается на множество позиций может включать непрерывный интервал в таблице удлинений затравки из позиций эталонной последовательности, которые совпадают с удлиненной затравкой из запроса. В альтернативном варианте осуществления в других реализациях информация, которая ссылается на множество позиций может включать один или более прерывистых интервалов в таблице удлинений затравки из позиций эталонной последовательности, совпадающих с затравкой из запроса.

[0140] В таких случаях компьютерная система может получать одну или более совпадающих позиций эталонной последовательности из таблицы удлинений затравки, идентифицированные с использованием записи об интервале. Полученные одна или более позиций эталонной последовательности могут быть добавлены к набору (455) совпадений с затравкой. В некоторых вариантах осуществления добавление одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой может включать в себя получение и хранение данных, представляющих одну или более совпадающих позиций эталонной последовательности, в позиции на запоминающем устройстве, выделенном для хранения набора совпадений с затравкой. В других вариантах осуществления добавление одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой может включать в себя хранение данных, например указателя, который ссылается на интервал(-ы) в таблице удлинений затравки, в которой хранится одна или более позиций эталонной последовательности. Соответственно, набор совпадений с затравкой может представлять собой позицию в хранилище, где хранится набор идентифицированных и полученных совпадающих позиций эталонной последовательности. В альтернативном варианте осуществления набор совпадений с затравкой может включать одну или более позиций в хранилище, где хранятся ссылки на одну или более совпадающих позиций эталонной последовательности. Компьютерная система может завершать этот случай процесса 400 на этапе 460 при добавлении одной или более совпадающих позиций эталонной последовательности, идентифицированной записью об интервале, к совпадениям затравки.

[0141] В других случаях после того, как компьютерная система определит (415), что в ответ включены по меньшей мере (i) запись об удлинении, (ii) запись об интервале, или (iii), или обе эти записи, компьютерная система может решать (430), что не нужен доступ к таблице удлинений затравки для получения одной или более совпадающих позиций эталонной последовательности. Определение с помощью компьютерной системы, что не нужно обращаться к таблице удлинений затравки для получения одной или более совпадающих позиций эталонной последовательности, может быть основано на различных факторах. Например, в некоторых вариантах осуществления компьютерная система может решать не осуществлять доступ к таблице удлинений затравки для получения совпадающих позиций эталонной последовательности, идентифицированных записью об интервале, если в результате ответа получена запись об удлинении. Такое определение может быть предпочтительным, поскольку удлиненная затравка, вероятно, даст меньший набор совпадающих позиций эталонной последовательности по сравнению с набором совпадающих позиций эталонной последовательности, идентифицированных записью об интервале.

[0142] В качестве другого примера в других вариантах осуществления компьютерная система может решать не осуществлять доступ к таблице удлинений затравки для получения совпадающих позиций эталонной последовательности, идентифицированных записью об интервале, если компьютерная система определяет, что количество совпадающих позиций эталонной последовательности превышает заданное пороговое количество совпадающих позиций эталонной последовательности. Аналогичным образом в тех вариантах осуществления, в которых число совпадающих позиций эталонной последовательности, идентифицированных интервалом, превышает порог по числу совпадений, компьютерная система может решать не обращаться к таблице удлинений затравки.

[0143] Если компьютерная система решает 430 не обращаться к таблице удлинений затравки, компьютерная система может продолжать выполнение процесса 400 и определять 465, включены ли в полученный ответ запись об интервале и запись об удлинении. Если компьютерная система определяет 465, что в полученный ответ включены запись об интервале и запись об удлинении, компьютерная система может решать 435, следует ли хранить запись об интервале или информацию, описывающую запись об интервале, включенную в ответ на выполненный запрос, в качестве потенциального наилучшего интервала. Во время первой итерации процесса 400 для запроса, для которого начальную затравку еще не удлиняли, компьютерная система может решать хранить запись об интервале или информацию, описывающую запись об интервале, в месте для хранения наилучшего интервала на запоминающем устройстве в качестве потенциального наилучшего интервала. Поскольку такие записи об интервале встречаются при начальной итерации процесса 400 для запроса с неудлиненной первоначальной затравкой, никакие другие записи об интервалах не встречаются в ответах на другие запросы с одной или более последующими удлиненными затравками. Соответственно, первый интервал, полученный в ответ на запрос, содержащий первоначальную затравку, которая еще не была удлинена, должен быть «наилучшим интервалом», поскольку для сравнения еще не было выявлено никаких других интервалов.

[0144] Однако при последующих взаимодействиях в процессе 400 после принятия ответа на запрос, содержащий удлиненную затравку, компьютерная система может получать вторую запись об интервале из ответа на запрос, содержащий удлиненную затравку. В таких случаях компьютерная система может эвристически определять, следует ли использовать вторую запись об интервале для замены ранее сохраненного потенциального наилучшего интервала в месте для хранения наилучшего интервала. Определение, нужно ли оставлять ранее сохраненный потенциальный наилучший интервал или заменять потенциальный наилучший интервал на второй интервал или информацию, описывающую интервал, можно осуществлять путем применения одного или более эвристических правил, как описано со ссылкой на пример на ФИГ. 3. В некоторых вариантах осуществления эвристические правила могут включать одно или более эвристических правил многокомпонентности.

[0145] Хотя некоторые варианты осуществления настоящего описания могут относиться к итеративной оценке каждой последующей полученной записи об интервале по сравнению с ранее хранящимся потенциальным наилучшим интервалом для определения одного наилучшего интервала, который должен храниться для текущего чтения, на котором основана затравка из запроса, настоящее описание не должно быть ограничено этим. Вместо этого в некоторых вариантах осуществления все интервалы можно сохранять в хранилище интервалов, и позднее оценивать для использования в качестве дополнения к наборам совпадений с затравкой.

[0146] Компьютерная система может продолжать выполнение процесса 400 и создавать удлиненную затравку (440). Удлиненная затравка может быть сгенерирована на основании команд, включенных в запись об удлинении, полученную в ответ на запрос. Например, запись об удлинении может включать одну или более команд, при исполнении которых компьютером, таким как центральный процессор (ЦП) или графический процессор (ГП), исполняющим программные команды, или программируемая схема, ЦП, ГП или программируемая схема 162 могут удлинять затравку, использованную в хеш-запросе, охватившем хеш-позицию, хранящую запись об удлинении, на один или более нуклеотидов. В некоторых вариантах осуществления запись об удлинении может быть сгенерирована таким образом, чтобы запись об удлинении давала команду компьютеру симметрично удлинять затравку с каждого конца затравки. Соответственно, в качестве примера может быть сгенерирована запись об удлинении, дающая команду компьютеру, такому как ЦП, ГП или программируемая схема 162, удлинять затравку на два нуклеотида, четыре нуклеотида, шесть нуклеотидов или т.п. В таких вариантах осуществления симметричное удлинение затравки может быть достигнуто путем удлинения затравок на один нуклеотид на каждом соответствующем конце затравки, на два нуклеотида на каждом соответствующем конце затравки, на три нуклеотида на каждом соответствующем конце затравки или т.п. Однако настоящее описание не должно ограничиваться симметричным удлинением затравок. Вместо этого в настоящем описании также предусмотрено асимметричное удлинение затравки.

[0147] Компьютерная система может продолжать выполнение процесса 400 и генерировать 445 хеш-запрос, который включает удлиненную затравку. Затем компьютерная система может выполнять еще одну итерацию процесса 400 путем выполнения запроса с удлиненной затравкой на стадии 405, а затем продолжать выполнение процесса 400 вплоть до (a) завершения процесса на стадии 427 или 460 путем добавления одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой, завершения процесса на стадии 475 после принятия решения, хранить ли запись об интервале в качестве потенциального наилучшего интервала, или (c) завершения процесса на стадии 420 в результате одной или более ошибок, например ошибки удлинения затравки, из-за которой на выполненный запрос не принимается ответ, в который включена (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности.

[0148] В альтернативном варианте осуществления, если на стадии 465 компьютерная система определяет, что в полученный ответ не включены одновременно запись об интервале и запись об удлинении, компьютерная система может продолжать выполнение процесса 400 путем определения, включает ли полученный ответ запись об удлинении.

[0149] Если компьютерная система определяет, что в полученный ответ включена запись об удлинении, компьютерная система может продолжить выполнение процесса 400 и генерировать удлиненную затравку на стадии 440, создавать хеш-запрос 445, который включает удлиненную затравку, и выполнять еще одну итерацию процесса 400 путем выполнения запроса с удлиненной затравкой на стадии 405. Затем компьютерная система может продолжать выполнение процесса 400 вплоть до (а) завершения процесса на этапах 427, 420, 460, 475.

[0150] С другой стороны, если компьютерная система определяет, что в полученный ответ не включена запись об удлинении, компьютерная система может продолжать выполнение процесса 400 на стадии 470 путем решения, хранить ли запись об интервале или информацию, описывающую запись об интервале, в качестве потенциального наилучшего интервала. Компьютерная система может определить, сохранить ли запись об интервале в качестве потенциального наилучшего интервала на стадии 470 с использованием тех же процессов, описанных применительно к решению, следует ли хранить запись об интервале в качестве потенциального наилучшего интервала на стадии 435. Независимо от того, решит ли компьютерная система хранить запись об интервале в качестве потенциального наилучшего интервала на стадии 470, процесс 400 завершается на стадии 475.

[0151] Может быть реализован по меньшей мере один вариант процесса 400, причем на стадии 470 компьютерная система вместо этого определяет, включена ли в полученный ответ запись об интервале. В таких случаях логичной будет возможность продолжения выполняемого компьютерной системой процесса на стадии 470, если компьютерная система определяет, что в полученный ответ включена запись об интервале. В альтернативном варианте осуществления, если компьютерная система определяет, что в полученный ответ не включена запись об интервале, процесс продолжится на стадии 440 генерированием удлиненной затравки. Аналогичным образом могут быть реализованы и другие варианты процесса 400, которые соответствуют сущности и объему настоящего описания.

[0152] На ФИГ. 5 представлена блок-схема процесса 500 выполнения итеративного оперативного гибкого удлинения затравки для геномного картирования на основе хеш-таблицы на каждой затравке чтения. По существу процесс 500 может включать в себя получение чтения, созданного секвенатором (505) нуклеиновых кислот, определение позиции окна доступа к затравке, причем окно доступа к затравке идентифицирует затравку в чтении (510), генерирование хеш-запроса, который включает затравку, идентифицированную окном (515) доступа к затравке, и начало выполнения процесса 400, описанного на ФИГ. 4 на стадии 410, путем выполнения созданного хеш-запроса и продолжения итеративного выполнения процесса 400 вплоть до завершения (520) процесса 400, определения, включает ли чтение другую затравку (525), и если определено, что чтение включает другую затравку (525), изменение положения окна доступа к затравке для идентификации другой затравки (530) и выполнение стадии 515 для создания хеш-запроса с использованием другой затравки (515).

[0153] Процесс 500 может продолжаться выполнением цикла обработки на стадиях 515, 520, 525 и 530 до определения на стадии 525, что чтение, полученное на стадии 505, не включает другой затравки, подлежащей картированию и выравниванию с использованием процесса 400. В таких случаях может быть решено, следует ли дополнять текущий набор совпадений с затравкой чтения, с использованием наилучшего интервала (535). Если принято решение использовать наилучший интервал для добавления к текущему набору совпадений с затравкой на стадии 535, процесс 500 может продолжаться на стадии 540 путем обработки наилучшего интервала (540), пополнения текущего набора совпадений с затравкой с использованием одной или более совпадающих позиций эталонной последовательности, полученных из части таблицы удлинений затравки, идентифицированных с использованием наилучшего интервала (545), и определения 550, имеется ли другое чтение, готовое к картированию и выравниванию с использованием процесса 500. Если отсутствует другое чтение, подготовленное к картированию и выравниванию, процесс 500 завершается на стадии 555. В альтернативном варианте осуществления, если имеется еще одно чтение, готовое к картированию и выравниванию с использованием процесса 500, процесс 500 продолжается на стадии 505 получением другого чтение, готового к картированию и выравниванию. Затем процесс 500 может итеративно продолжать выполнение процесса 500 до определения на стадии 550, что больше нет чтений, готовых к картированию и выравниванию с использованием процесса 500.

[0154] Процесс 500 будет описан ниже более подробно как выполняемый компьютерной системой из одного или более компьютеров. Один или более компьютеров могут включать в себя, например, блок 170 картирования и выравнивания. Для целей настоящего описания один или более компьютеров могут включать в себя ЦП или ГП, который выполнен с возможностью получения и выполнения программных команд для реализации конкретной запрограммированной функциональной возможности, описанной в программных командах. В альтернативном или дополнительном варианте осуществления один или более компьютеров могут включать программируемую схему, выполненную таким образом, что аппаратные цифровые логические схемы программируемой схемы выполнены с возможностью реализации конкретной запрограммированной функциональности в аппаратном обеспечении.

[0155] Компьютерная система может начинать выполнение процесса 500 путем получения данных, представляющих чтение нуклеиновой кислоты (также называемого в настоящем документе «чтением»), генерируемое секвенатором (505) нуклеиновых кислот. Чтение может быть принято компьютерной системой в качестве входных данных и от секвенатора нуклеиновых кислот после генерирования этого чтения секвенатором нуклеиновых кислот. В альтернативном или дополнительном варианте осуществления чтение, генерируемое секвенатором нуклеиновых кислот, может храниться в запоминающем устройстве, доступном для компьютерной системы. Затем компьютерная система 500 может получать сохраненное(-ые) чтение(-я) путем обращения к памяти и извлечения одного или более чтений из запоминающего устройства. Например, чтение может включать набор нуклеотидов, такой как ACGTTTAGC. Данный пример включает чтение из 9 нуклеотидов. Однако чтение из 9 нуклеотидов используют только в качестве примера. Вместо ограничения 9 нуклеотидами, чтения, приводимые в настоящем описании, могут иметь любое количество нуклеотидов, включая, без ограничений, 5 оснований или нуклеотидов, 10 оснований или нуклеотидов, 12 оснований или нуклеотидов, 15 оснований или нуклеотидов, 18 оснований или нуклеотидов, 21 основание или нуклеотид, 25 оснований или нуклеотидов, 35 оснований или нуклеотидов, 50 оснований или нуклеотидов, 100 оснований нуклеотидов, 150 оснований или нуклеотидов, 1000 оснований или нуклеотидов, 1 000 000 оснований или нуклеотидов или даже большее количество оснований или нуклеотидов.

[0156] Компьютерная система может продолжать выполнение процесса 500 определением позиции окна (510) доступа к затравке. Окно доступа к затравке может быть использовано для идентификации нуклеотидных затравок, которые состоят из подгруппы нуклеотидов чтения. Примером затравки является набор последовательных нуклеотидов GTTTA, представляющих собой затравку чтения ACGTTTAGC. Хотя набор последовательных нуклеотидов GTTTA представляет собой пример непрерывной затравки чтения ACGTTTAGC, настоящее описание не обязательно должно быть ограничено этим. Напротив, в некоторых вариантах осуществления с использованием систем и процессов, описанных в настоящем описании, можно получать и анализировать затравки, не являющиеся непрерывными. Например, прерывистая затравка, такая как G_T_A, может также быть получена из чтения ACGTTTAGC и проанализирована с использованием систем и способов, описанных в настоящем документе. В таких вариантах осуществления в системах и способах настоящего описания могут быть рассмотрены пропущенные позиции, представленные символом подчеркивания «_», в качестве универсального заменителя, который может соответствовать любому основанию или нуклеотиду.

[0157] Окно доступа к затравке может быть выполнено так, чтобы иметь любое количество оснований или нуклеотидов, которое меньше длины чтения. Окно доступа к затравке может быть выполнено с возможностью перемещения вперед или назад по последовательности чтения для идентификации обрабатываемой затравки чтения. При необходимости использования прерывистых затравок окно доступа к затравке может быть соответствующим образом настроено. Например, окно доступа к затравке может быть выполнено с возможностью идентификации девятинуклеотидной прерывистой затравки с универсальным символом, вставленным в позицию 6-го нуклеотида и позицию 8-го нуклеотида.

[0158] Компьютерная система может продолжать выполнение процесса 500 генерированием хеш-запроса, который включает затравку, идентифицированную окном (515) доступа к затравке. В некоторых вариантах осуществления хеш-запрос может состоять только из затравки GTTTA чтения, такого как ACGTTTAGC. В других вариантах осуществления к затравке из чтения образца можно добавлять дополнительные данные, метаданные или т.п. для перевода чтения в формат, который можно использовать для поиска в хеш-таблице.

[0159] Компьютерная система может продолжать выполнение процесса 500 путем выполнения процесса 400, показанного на ФИГ. 4 (520), для картирования и выравнивания затравки из сгенерированного запроса с одной или более позициями эталонной последовательности. Компьютерная система начинает выполнение процесса 400 с выполнения на стадии 410 хеш-запроса, сгенерированного на стадии 515. Затем компьютерная система может продолжать итеративное выполнение процесса 400 до завершения процесса 400 на стадии 420, 427, 460 или 475, с возможным добавлением совпадающих позиций эталонной последовательности к набору совпадений с затравкой на стадии 425 или 455.

[0160] После завершения процесса 400 компьютерная система может определять, включена ли в чтение, полученное на стадии 505, другая затравка (525). В некоторых вариантах осуществления определение, включена ли в чтение другая затравка, включает в себя рассмотрение всех возможных положений окна доступа к затравке на чтении. В альтернативном варианте осуществления определение, включена ли в чтение другая затравка, может включать в себя рассмотрение только заданного набора всех возможных положений окна доступа к затравке, например только четных положений окна доступа к затравке или только нечетных положений окна доступа к затравке. Соответственно, в настоящем описании не требуется оценивание каждой затравки чтения с помощью процесса 500. Вместо этого в некоторых вариантах осуществления компьютерная система может определять на стадии 505, имеется ли еще одна затравка из заданного набора затравок чтения, которую нужно оценить с помощью процесса 500.

[0161] Если компьютерная система на стадии 525 определяет, что в чтение включена еще одна затравка, компьютерная система может корректировать положение окна доступа к затравке для идентификации другой затравки (530), и компьютерная система может выполнять стадию 515 с генерированием хеш-запроса с другой затравкой, идентифицированной скорректированным окном (515) доступа к затравке. Коррекция положения окна доступа к затравке может включать в себя, например, перемещение окна доступа к затравке вперед вдоль чтения, полученного на стадии 505, на одно или более основание или нуклеотид. Компьютерная система может продолжать выполнение цикла обработки на стадиях 515, 520, 525 и 530 до определения с помощью компьютерной системы на стадии 525, что чтение, полученное на стадии 505, не включает другой затравки, подлежащей картированию и выравниванию с использованием процесса 400.

[0162] После того как компьютерная система определит, что в чтение, полученное на стадии 505, не включена другая затравка, подлежащая картированию и выравниванию, компьютерная система может определять, следует ли дополнять текущий набор совпадений с затравкой чтения с использованием наилучшего интервала (535). В некоторых случаях, если компьютерная система определяет, что набор совпадений с затравкой дополнять не следует, компьютерная система может определять (550), имеется ли еще чтение, готовое к картированию и выравниванию с помощью процесса 500. В таких случаях, если компьютерная система определяет наличие еще одного чтения, готового к картированию и выравниванию, компьютерная система может продолжать выполнение процесса 500 на стадии 505 получением этого другого чтения, готового к картированию и выравниванию. Затем компьютерная система может продолжать итеративное выполнение процесса 500 до определения на стадии 550, что больше нет чтений, готовых к картированию и выравниванию с использованием процесса 500.

[0163] В альтернативном варианте осуществления в других случаях компьютерная система может решать, что текущий набор совпадений с затравкой чтения должен быть дополнен с использованием одной или более совпадающих позиций эталонной последовательности, идентифицированных наилучшим интервалом. Компьютерная система может решать, что текущий набор совпадений с затравкой должен быть дополнен с использованием одной или более совпадающих позиций эталонной последовательности, идентифицированных наилучшим интервалом, путем применения одного или более эвристических правил к (i) длине удлиненной затравки, запрос с которой дал наилучший интервал, (ii) длине одной или более совпадающих позиций эталонной последовательности в затравке, (iii) количеству созданных цепей-затравок или их комбинации. В некоторых вариантах осуществления эвристические правила могут определять одно или более независимых инициирующих условий, при выполнении которых компьютерная система обрабатывает наилучший интервал.

[0164] В качестве примера первое независимое инициирующее условие, которое может инициировать обработку компьютерной системой наилучшего интервала, заключается в определении, больше ли длина удлиненной затравки, запрос с которой вернул наилучший интервал, чем значение ориентир-для-интервала(60), выраженное в основаниях или нуклеотидах, или равна ему. В данном примере пороговое значение ориентир-для-интервала(60) представляет собой заданное пороговое значение, которое может использовать компьютерная система для оценки длины удлиненных затравок, дающих наилучший интервал. В данном примере длина давшей наилучший интервал удлиненной затравки, которую проверяет компьютерная система, составляет шестьдесят нуклеотидов. Тем не менее настоящее описание не обязательно ограничено таким образом. Вместо этого для параметра ориентир-для-интервала() может быть задано любое значение. Если компьютерная система определяет, что условие ориентира-для-интервала() не выполнено, компьютерная система может оценивать другие инициирующие условия, чтобы определять, нужно ли обрабатывать наилучший интервал.

[0165] В качестве еще одного примера второе независимое инициирующее условие, которое может инициировать обработку компьютерной системой наилучшего интервала, заключается в определении, больше ли длина удлиненной затравки, запрос с которой вернул наилучший интервал, чем имеющая наибольшую длину обработанная совпадающая позиция эталонной последовательности, на по меньшей мере значение ориентир-для-интервала(8), выраженное в основаниях или нуклеотидах. В данном примере пороговое значение ориентир-для-интервала(8) представляет собой заданное пороговое значение, которое может быть использовано компьютерной системой для сравнительной оценки (i) длины удлиненной затравки, запрос с которой дал наилучший интервал, и (ii) позиций самой длинной совпадающей эталонной последовательности. В данном примере, если компьютерная система определяет, что удлиненная затравка, запрос с которой дал наилучший интервал, по длине на восемь или более оснований или нуклеотидов больше, чем любая совпадающая затравка, запускается обработка наилучшего интервала.

[0166] В качестве другого примера, третье независимое инициирующее условие, которое может инициировать обработку компьютерной системой наилучшего интервала, представляет собой определение, меньше ли количество цепей затравки, чем значение минимум-цепей-интервала(8). Цепь затравки может включать в себя группу имеющих сходное местоположение совпадений с позициями эталонной последовательности. В этом примере пороговое значение минимум-цепей-интервала(8) представляет собой заданное пороговое значение, которое можно использовать для оценки количества сгенерированных цепей затравки. В данном примере, если получено менее восьми цепей затравки, инициируется обработка наилучшего интервала.

[0167] Хотя описаны примеры трех независимых инициирующих условий для запуска обработки наилучшего интервала для дополнения набора совпадений с затравкой, настоящее описание не обязательно должно быть ограничено этим. Вместо этого могут быть разработаны другие инициирующие условия для запуска обработки наилучшего интервала, в зависимости от требований конкретной компьютерной системы.

Если компьютерная система решает на стадии 535 дополнить набор совпадений с затравкой, так как, например, были соблюдены одно или более пороговых значений из инициирующего условия для обработки наилучшего интервала, компьютерная система может решать использовать наилучший интервал для дополнения текущего набора совпадений с затравкой на стадии 535. Использование наилучшего интервала для дополнения текущего набора совпадений с затравкой может включать в себя обработку компьютерной системой наилучшего интервала (540). Обработка наилучшего интервала может включать в себя применение одного или более эвристических правил к наилучшему интервалу для идентификации одной или более совпадающих позиций эталонной последовательности, идентифицированных наилучшим интервалом и сохраненных в таблице удлинений затравки.

[0168] Например, компьютерная система может решать обрабатывать каждую из одной или более позиций эталонной последовательности, идентифицированных наилучшим интервалом, если число позиций эталонной последовательности, идентифицированных наилучшим интервалом, меньше значения максимум-совпадений-интервала(64) или равно ему. В этом примере, если компьютерная система определяет, что идентифицированный наилучший интервал равен шестидесяти четырем совпадающим позициям эталонной последовательности или менее, компьютерная система может получать все совпадающие позиции эталонной последовательности, определенные наилучшим интервалом, из таблицы удлинений затравки с использованием наилучшего интервала. В альтернативном варианте осуществления, если компьютерная система определяет, что наилучший интервал идентифицирует более шестидесяти четырех совпадающих позиций эталонной последовательности, компьютерная система может случайным образом получать выборку-совпадений-интервала(32) из набора совпадающих позиций эталонной последовательности, идентифицированных наилучшим интервалом.

[0169] Случайное получение порогового количества в тридцать две совпадающие позиции эталонной последовательности может включать в себя случайный или детерминистический псевдослучайный выбор для получения порогового количества в тридцать две совпадающих позиции эталонной последовательности из таблицы удлинений затравки с использованием наилучшего интервала. Наилучший интервал может включать данные, идентифицирующие (i) одно или более конечных и начальных положений в таблице удлинений затравки, (ii) одно или более начальных положений и одно или более смещений, или их комбинации. Хотя описаны примеры порогового значения, такие как шестьдесят четыре совпадающих с эталоном позиции и 32 случайно отобранных совпадения, настоящее описание не обязательно должно быть ограничено этим. Вместо этого для достижения преимуществ настоящего описания можно использовать другие пороги, имеющие другие числовые значения.

[0170] Совпадающие позиции эталонной последовательности, полученные с использованием наилучшего интервала, можно использовать для пополнения текущего набора 545 совпадений с затравкой. Посредством такого пополнения набора соответствий для затравки с использованием наилучшего интервала можно решать такие проблемы, как проблемы некартированных чтений или проблемы высокодостоверного неправильного картирования, из-за которых соответственно в наборе совпадений с затравкой могут не сохраниться совпадающие позиции эталонной последовательности или в наборе совпадений с затравкой может сохраниться очень малое количество совпадающих позиций эталонной последовательности. Совпадающие позиции эталонной последовательности, возможно, могли быть получены или могут быть получены из части таблицы удлинений затравки, идентифицированной наилучшим интервалом (540).

[0171] После пополнения набора совпадений с затравкой компьютерная система может определять, имеется ли еще одно чтение, готовое к картированию и выравниванию с помощью процесса 500. Если имеется еще одно чтение, готовое к картированию и выравниванию, компьютерная система продолжает выполнение процесса 500 после получения этого другого чтения. В альтернативном варианте осуществления, если другое чтение, готовое к картированию и выравниванию, отсутствует, процесс 500 может завершаться на этапе 555.

[0172] Следует отметить, что в примере, описанном со ссылкой на процесс 500, наилучший интервал оценивают, чтобы определить, можно ли использовать наилучший интервал (или его часть) для пополнения набора совпадений с затравкой. Однако нет требования, чтобы в хранилище наилучших интервалов хранился только один наилучший интервал. В некоторых вариантах осуществления компьютерная система может способствовать хранению более одного наилучшего интервала в хранилище наилучших интервалов. Например, в некоторых вариантах осуществления можно отслеживать до 2 наилучших интервалов. В некоторых вариантах осуществления можно отслеживать до N наилучших интервалов. В таких вариантах осуществления, если хранятся N > 1 лучших интервалов, критерии определения сохранения интервалов могут включать оценку взаимоотношений между потенциальными интервалами и/или связанными с ними удлиненными затравками или среди них, например требование, чтобы N наилучших интервалов были ассоциированы с удлиненными затравками, которые не накладываются друг на друга в пределах чтения. В некоторых вариантах осуществления компьютерная система может даже выбирать совпадающие позиции эталонной последовательности из множества разных наилучших интервалов. Такой выбор совпадающих позиций эталонной последовательности из множества разных наилучших интервалов можно выполнять случайным образом, псевдослучайным образом или с применением одного или более эвристических правил.

Компоненты системы

[0173] На ФИГ. 6 представлена схема компонентов системы, которые можно использовать для реализации описанных в настоящем документе систем, относящихся к гибким удлинениям затравок, при геномном картировании на основе хеш-таблицы.

[0174] Вычислительное устройство 600 должно представлять собой различные формы цифровых компьютеров, таких как ноутбуки, настольные компьютеры, рабочие станции, карманные персональные компьютеры, серверы, блейд-серверы, мэйнфреймы и другие подходящие компьютеры. Вычислительное устройство 650 должно представлять собой различные формы мобильных устройств, таких как карманные персональные компьютеры, сотовые телефоны, смартфоны и другие аналогичные вычислительные устройства. Кроме того, вычислительное устройство 600 или 650 может включать в себя флэш-накопители с универсальной последовательной шиной (USB). Во флэш-накопителях USB могут храниться операционные системы и другие приложения. Флэш-накопители USB могут включать в себя компоненты ввода/вывода, такие как беспроводной передатчик или USB-разъем, который может быть вставлен в USB-порт другого вычислительного устройства. Представленные здесь компоненты, их соединения и взаимоотношения, а также их функции являются только примерами и не предназначены для ограничения вариантов осуществления изобретения, описанных и/или заявленных в настоящем документе.

[0175] Вычислительное устройство 600 включает в себя процессор 602, память 604, устройство 608 хранения, высокоскоростной интерфейс 608, соединяющийся с памятью 604 и высокоскоростными расширительными портами 610, и низкоскоростной интерфейс 612, соединяющийся с низкоскоростной шиной 614 и устройством 608 хранения. Все компоненты 602, 604, 608, 608, 610 и 612 соединены друг с другом с помощью различных шин, и могут быть установлены на общей материнской плате или при необходимости другими способами. Процессор 602 может обрабатывать команды, предназначенные для выполнения в вычислительном устройстве 600, включая команды, хранящиеся в памяти 604 или на устройстве 608 хранения, для отображения графической информации графического пользовательского интерфейса на внешнем устройстве ввода/вывода, таком как дисплей 616, соединенный с высокоскоростным интерфейсом 608. В других вариантах осуществления при необходимости можно использовать множество процессоров и/или множество шин вместе с множеством запоминающих устройств и типов памяти. Кроме того, множество вычислительных устройств 600 могут быть соединены, причем каждое устройство обеспечивает часть необходимых операций, например это может быть банк серверов, группа блейд-серверов или многопроцессорная система.

[0176] Информация памяти 604 хранится в вычислительном устройстве 600. В одном варианте осуществления память 604 представляет собой блок или блоки энергозависимой памяти. В другом варианте осуществления память 604 представляет собой блок или блоки энергонезависимой памяти. Память 604 может также представлять собой другую форму машиночитаемого носителя, такую как магнитный или оптический диск.

[0177] Устройство 608 хранения выполнено с возможностью обеспечения большой емкости хранения для вычислительного устройства 600. В одном варианте осуществления устройство 608 хранения может представлять собой или содержать машиночитаемый носитель, такой как устройство с гибким диском, устройство с жестким диском, устройство с оптическим диском или устройство с лентой, флэш-память или другое аналогичное твердотельное запоминающее устройство или массив устройств, включая устройства в сети хранения данных или в других конфигурациях. Компьютерный программный продукт может быть на практике реализован на носителе информации. Компьютерный программный продукт может также содержать команды, которые при их исполнении осуществляют один или более способов, таких как описанные выше. Носитель информации представляет собой компьютерочитаемый или машиночитаемый носитель, такой как память 604, устройство 608 хранения данных или память на процессоре 602.

[0178] Высокоскоростной контроллер 608 управляет операциями с большой пропускной способностью для вычислительного устройства 600, а низкоскоростной контроллер 612 управляет операциями с меньшей пропускной способностью. Такое распределение функций является лишь примером. В одном варианте осуществления высокоскоростной контроллер 608 соединен с памятью 604, дисплеем 616, например, через графический процессор или ускоритель, и с высокоскоростными расширительными портами 610, в которые можно устанавливать различные платы расширения (не показаны). В этом варианте осуществления низкоскоростной контроллер 612 соединен с устройством 608 хранения и низкоскоростным расширительным портом 614. Низкоскоростной расширительный порт, который может включать в себя различные коммуникационные порты, например USB, Bluetooth, Ethernet, беспроводной Ethernet, может быть соединен с одним или более устройствами ввода/вывода, такими как клавиатура, указательное устройство, пара микрофон/динамик, сканер или сетевое устройство, такое как коммутатор или маршрутизатор, например, через сетевой адаптер. Вычислительное устройство 600 может быть реализовано в нескольких различных формах, как показано на фигуре. Например, оно может быть реализовано как стандартный сервер 620 или многократно, в виде группы таких серверов. Оно может также быть реализовано как часть стоечной серверной системы 624. Кроме того, оно может быть реализовано на персональном компьютере, таком как ноутбук 622. В альтернативном варианте осуществления компоненты вычислительного устройства 600 могут быть объединены с другими компонентами в мобильном устройстве (не показано), таком как устройство 650. Каждое из таких устройств может содержать одно или более вычислительных устройств 600, 650, и вся система может состоять из множества вычислительных устройств 600, 650, взаимодействующих друг с другом.

[0179] Вычислительное устройство 600 может быть реализовано в нескольких различных формах, как показано на фигуре. Например, оно может быть реализовано как стандартный сервер 620 или многократно, в виде группы таких серверов. Оно может также быть реализовано как часть стоечной серверной системы 624. Кроме того, оно может быть реализовано на персональном компьютере, таком как ноутбук 622. В альтернативном варианте осуществления компоненты вычислительного устройства 600 могут быть объединены с другими компонентами в мобильном устройстве (не показано), таком как устройство 650. Каждое из таких устройств может содержать одно или более вычислительных устройств 600, 650, и вся система может состоять из множества вычислительных устройств 600, 650, взаимодействующих друг с другом.

[0180] Вычислительное устройство 650 включает в себя процессор 652, память 664 и устройство ввода/вывода, такое как, помимо прочего, дисплей 654, коммуникационный интерфейс 666 и приемопередатчик 668. Устройство 650 может также быть снабжено устройством хранения, таким как микропривод или другое устройство, для обеспечения дополнительной возможности хранения. Все компоненты 650, 652, 664, 654, 666 и 668 соединяют друг с другом с помощью различных шин, и некоторые из компонентов могут быть установлены на общей материнской плате или иными способами, в зависимости от ситуации.

[0181] Процессор 652 может выполнять команды, имеющиеся в вычислительном устройстве 650, включая команды, хранящиеся в памяти 664. Процессор может быть реализован в виде набора микросхем, включая отдельные и многокомпонентные аналоговые и цифровые процессоры. Кроме того, процессор может быть реализован с использованием любой из ряда архитектур. Например, процессор 610 может представлять собой процессор CISC (вычислительное устройство с полным набором команд), процессор RISC (вычислительное устройство с сокращенным набором команд) или процессор MISC (вычислительное устройство с минимальным набором команд). Процессор может обеспечивать, например, координацию других компонентов устройства 650, таких как управление пользовательскими интерфейсами, запуск приложений устройством 650, и беспроводную связь с устройством 650.

[0182] Процессор 652 может обмениваться данными с пользователем через интерфейс 658 управления и интерфейс 656 дисплея, соединенный с дисплеем 654. Дисплей 654 может представлять собой, например, дисплей типа TFT (жидкокристаллический дисплей на тонкопленочных транзисторах) или типа OLED (на органических светоизлучающих диодах), или другие подходящие технологии отображения. Интерфейс 656 дисплея может содержать соответствующую схему для приведения дисплея 654 в действие и для представления графической и другой информации пользователю. Интерфейс 658 управления может принимать команды от пользователя и преобразовывать их для передачи процессору 652. Кроме того, может быть предусмотрен внешний интерфейс 662, сообщающийся с процессором 652 для обеспечения устройства 650 связью ближнего радиуса действия с другими устройствами. Внешний интерфейс 662 может обеспечивать в некоторых вариантах осуществления, например, проводную связь, или в других вариантах осуществления беспроводную связь, и можно также использовать множество интерфейсов.

[0183] Информация памяти 664 хранится в вычислительном устройстве 650. Память 664 может быть реализована в виде одного или более машиночитаемого носителя или носителей, блока или блоков энергозависимой памяти, или блока или блоков энергонезависимой памяти. Кроме того, может быть предусмотрена расширительная память 674, соединенная с устройством 650 посредством расширительного интерфейса 672, который может включать в себя, например, интерфейс карты SIMM (модуль с однорядным расположением микросхем памяти). Такая расширительная память 674 может обеспечивать устройство 650 дополнительным пространством хранения, или может также хранить приложения или другую информацию для устройства 650. В частности, расширительная память 674 может включать команды для выполнения или для дополнения описанных выше процессов, а может также включать защищенную информацию. Таким образом, например, расширительная память 674 может быть обеспечена в качестве защищенного модуля для устройства 650 и может быть запрограммирована командами, которые позволяют использовать устройство 650 защищенным образом. Кроме того, с помощью плат SIMM можно передавать безопасные приложения, а также дополнительную информацию, например размещать идентификационную информацию на карте SIMM без возможности компрометации.

[0184] Память может включать в себя, например, флэш-память и/или энергонезависимую оперативную память (NVRAM), как описано ниже. В одном варианте осуществления компьютерный программный продукт на практике реализован на носителе информации. Компьютерный программный продукт содержит команды, при исполнении которых осуществляется один или более способов, такие как описанные выше. Информационный носитель представляет собой компьютерочитаемый или машиночитаемый носитель, такой как память 664, расширительная память 674 или память на процессоре 652, причем информация может быть принята, например, посредством приемопередатчика 668 или внешнего интерфейса 662.

[0185] Устройство 650 может обмениваться данными беспроводным способом через коммуникационный интерфейс 666, в который при необходимости может быть включена схема для обработки цифровых сигналов. Коммуникационный интерфейс 666 связи может обеспечивать связь в различных режимах или протоколах, таких как, помимо прочего, голосовые звонки GSM, SMS, EMS или MMS сообщения, CDMA, TDMA, PDC, WCDMA, CDMA2000 или GPRS. Такую передачу данных можно осуществлять, например, при помощи радиочастотного приемопередатчика 668. Кроме того, возможна связь ближнего радиуса действия, например, с помощью Bluetooth, Wi-Fi или другого подобного приемопередатчика (не показан). Кроме этого, модуль 670 приемника GPS (глобальной системы позиционирования) может передавать дополнительные относящиеся к навигации и местоположению беспроводные данные на устройство 650, которые можно использовать при необходимости в приложениях, работающих на устройстве 650.

[0186] Устройство 650 может также передавать звуковой сигнал с использованием аудиокодека 660, который может принимать речевую информацию от пользователя и преобразовывать ее в пригодную для использования цифровую информацию. Аудиокодек 660 может также генерировать звуковой сигнал для пользователя, например, через динамик, например через гарнитуру устройства 650. Такой звуковой сигнал может представлять собой звук от голосовых телефонных звонков, может представлять собой записанный звук, например голосовые сообщения, музыкальные файлы и т.п., а может также включать в себя звук, создаваемый приложениями, работающими на устройстве 650.

[0187] Вычислительное устройство 650 может быть реализовано в нескольких различных формах, как показано на фигуре. Например, оно может быть реализовано в виде сотового телефона 680. Оно может также быть реализовано как часть смартфона 682, карманного персонального компьютера или другого подобного мобильного устройства.

[0188] Различные варианты осуществления систем и способов, описанных в настоящем документе, могут быть реализованы в виде цифровой электронной схемы, интегральной схемы, специально разработанных ASIC (специализированных интегральных схем), компьютерного аппаратного обеспечения, микропрограммного обеспечения, программного обеспечения и/или в виде комбинации таких вариантов осуществления. Данные различные реализации могут включать реализацию в одной или более компьютерных программах, выполненных с возможностью исполнения и/или интерпретации в программируемой системе, включающей в себя по меньшей мере один программируемый процессор, который может быть специализированным или общего назначения, присоединенный к системе хранения для приема от нее данных и команд и передачи в нее данных и команд, по меньшей мере одно устройство ввода и по меньшей мере одно устройство вывода.

[0189] Эти компьютерные программы (также именуемые программами, программным обеспечением, программными приложениями или кодом), включают в себя машинные команды для программируемого процессора и могут быть реализованы на высокоуровневом процедурном и/или объектно-ориентированном языке программирования, и/или на ассемблерном/машинном языке. Используемые в настоящем документе термины «машиночитаемый носитель», «компьютерочитаемый носитель» относятся к любому компьютерному программному продукту, аппарату и/или устройству, например такому как магнитные диски, оптические диски, запоминающее устройство, программируемые логические устройства (PLD), используемые для передачи машинных команд и/или данных на программируемый процессор, включая машиночитаемый носитель, который принимает машинные команды в качестве машиночитаемого сигнала. Термин «машиночитаемый сигнал» относится к любому сигналу, используемому для передачи машинных команд и/или данных на программируемый процессор.

[0190] Для обеспечения взаимодействия с пользователем описанные в настоящем документе системы и методы могут быть реализованы на компьютере, имеющем устройство отображения, например КЛТ- (катодно-лучевая трубка) или ЖК- (жидкокристаллический) монитор, для отображения информации пользователю, и клавиатуру и указывающее устройство, например мышь или трекбол, с помощью которых пользователь может вводить в компьютер входные данные. Можно также использовать другие виды устройств для обеспечения взаимодействия с пользователем, например, предоставляемая пользователю обратная связь может принимать форму любой сенсорной обратной связи, например визуальной обратной связи, слуховой обратной связи или тактильной обратной связи, и входные данные от пользователя могут поступать в любой форме, включая звуковые, речевые или тактильные входные данные.

[0191] Описанные в настоящем документе системы и методы могут быть реализованы в компьютерной системе, которая включает в себя серверный компонент, например сервер данных, или включает в себя промежуточный компонент, например сервер приложений, или включает в себя клиентский компонент (например, компьютер-клиент с графическим интерфейсом пользователя или веб-браузером, с помощью которых пользователь может взаимодействовать с реализацией описанных в настоящем документе систем и методов), либо любую комбинацию таких серверных, промежуточных и клиентских компонентов. Компоненты системы могут быть связаны между собой любой формой или средой цифрового обмена данными, например сетью связи. К примерам сетей связи относятся локальная вычислительная сеть (LAN), глобальная сеть (WAN) и Интернет.

[0192] Компьютерная система может включать в себя клиенты и серверы. Клиент и сервер по существу удалены друг от друга и, как правило, взаимодействуют через сеть связи. Функциональная зависимость клиента и сервера возникает благодаря компьютерным программам, выполняемым на соответствующих компьютерах и имеющим функциональную зависимость клиент-сервер друг от друга.

ПРИМЕРЫ

[0193] Описание дополнительно раскрыто в следующих примерах, которые не ограничивают объем формулы изобретения.

Пример 1. Сравнение процентной доли некартированных чтений между системами, в которых используют гибкое удлинение затравки, и системами, в которых не используют гибкое удлинение затравки

[0194] В данном примере для секвенирования конкретного образца использовали различные секвенаторы нуклеиновых кислот, включая секвенатор HiSeq® 2500, секвенатор HiSeq® X и секвенатор NovaSeq®. Затем использовали платформу DRAGEN™ для картирования чтений, полученных каждым соответствующим секвенатором, с гибким удлинением затравок, как описано в настоящем документе, и без гибкого удлинения затравок. После картирования компьютерная система определяла процентную долю некартированных чтений, полученных в результате операций картирования для каждого секвенатора.

[0195] Платформа DRAGEN™ представляет собой блок картирования и выравнивания, реализованный в аппаратной схеме с программируемой пользователем вентильной матрицей (FPGA). В платформе DRAGEN™ v7 в настоящее время не используется гибкое удлинение затравки, описанное в настоящем документе, тогда как в платформе DRAGEN™ v8 используется гибкое удлинение затравки. Хотя платформа DRAGEN™, используемая в настоящем документе, была реализована в виде FPGA, в целом платформа DRAGEN™ может также быть реализована в виде других интегральных схем, таких как специализированная интегральная схема (ASIC).

[0196] В частности, секвенатор HiSeq® 2500 использовали для секвенирования образца DNA_Nexus_hiseq2500, секвенатор HiSeq® X использовали для секвенирования образца DNA_Nexus_hiseqX, а секвенатор NovaSeq® использовали для секвенирования образца DNA_Nexus_NovaSeq, образца NovaSeq_NA12878_rep1, образца NovaSeq_TruSeq-nano-550 и образца AWS_HG005_40x. Образец AWS_HG005_40X был взят у субъекта HG005. Все остальные образцы были взяты у субъекта HG001.

[0197] На ФИГ. 7 представлена гистограмма 700, отображающая данные результатов тестирования в виде процентной доли некартированных чтений в системе, использующей способ гибкого удлинения затравки, описанный в настоящем документе, по сравнению с системой, не использующей способ гибкого удлинения затравки. Гистограмма 700 представляет собой графическое представление результатов тестов 710, 720, 730, 740, 750 и 760, сравнивающих результаты операций картирования, выполненных на геномных чтениях, полученных различными секвенирующими устройствами производства Illumina, Inc.

[0198] В первом примере в результатах 710 теста показано, что процентная доля некартированных чтений, полученных 710b когда секвенатор HiSeq® 2500 секвенирует образец DNA_Nexus_hiseq2500, и использует гибкое удлинение затравки, описанное в одном или более вариантах осуществления настоящего документа, во время картирования значительно меньше процентной доли некартированных чтений, получаемых 710a, когда секвенатор HiSeq® 2500 секвенирует образец DNA_Nexus_hiseq2500 без гибкого удлинения затравки, описанного в одном или более вариантах осуществления в настоящем документе, во время картирования.

[0199] Во втором примере в результатах 720 теста показано, что процентная доля некартированных чтений, полученных 720b когда секвенатор NovaSeq® секвенирует образец DNA_Nexus_NovaSeq, и использует гибкое удлинение затравки, описанное в одном или более вариантах осуществления настоящего документа, во время картирования значительно меньше процентной доли некартированных чтений, получаемых 720a, когда секвенатор NovaSeq секвенирует образец DNA_Nexus_NovaSeq без гибкого удлинения затравки, описанного в одном или более вариантах осуществления в настоящем документе, во время картирования.

[0200] В третьем примере в результатах 730 теста показано, что процентная доля некартированных чтений, полученных 730b, когда секвенатор HiSeq® X секвенирует образец DNA_Nexus_hiseqX, и использует гибкое удлинение затравки, описанное в одном или более вариантах осуществления настоящего документа, во время картирования значительно меньше процентной доли некартированных чтений, получаемых 730a, когда секвенатор HiSeq® X секвенирует образец DNA_Nexus_hiseqX без гибкого удлинения затравки, описанного в одном или более вариантах осуществления в настоящем документе, во время картирования.

[0201] В четвертом примере в результатах 740 теста показано, что процентная доля некартированных чтений, полученных 740b, когда секвенатор NovaSeq® секвенирует образец NovaSeq_NA12878_rep1, и использует гибкое удлинение затравки, описанное в одном или более вариантах осуществления настоящего документа, во время картирования значительно меньше процентной доли некартированных чтений, получаемых 740a, когда секвенатор NovaSeq® секвенирует образец NovaSeq_NA12878_rep1 без гибкого удлинения затравки, описанного в одном или более вариантах осуществления в настоящем документе, во время картирования.

[0202] В пятом примере в результатах 750 теста показано, что процентная доля некартированных чтений, полученных 750b, когда секвенатор NovaSeq® секвенирует образец NovaSeq_TruSeq-nano-550, и использует гибкое удлинение затравки, описанное в одном или более вариантах осуществления настоящего документа, во время картирования значительно меньше процентной доли некартированных чтений, получаемых 750a, когда секвенатор NovaSeq® секвенирует образец NovaSeq_TruSeq-nano-550 без гибкого удлинения затравки, описанного в одном или более вариантах осуществления в настоящем документе, во время картирования.

[0203] В шестом примере в результатах 760 теста показано, что процентная доля некартированных чтений, полученных 760b, когда секвенатор NovaSeq® секвенирует образец AWS_HG005_40X, и использует гибкое удлинение затравки, описанное в одном или более вариантах осуществления настоящего документа, во время картирования значительно меньше процентной доли некартированных чтений, получаемых 760a, когда секвенатор NovaSeq® секвенирует образец AWS_HG005_40X без гибкого удлинения затравки, описанного в одном или более вариантах осуществления в настоящем документе, во время картирования.

[0204] Таким образом, реализация гибкого удлинения затравки с использованием хеш-таблиц, описанных в настоящем документе, позволяет добиться существенных улучшений характеристик в плане уменьшения доли некартированных чтений по сравнению с традиционными способами, в которых не генерируют или не используют хеш-таблицы, описанные в настоящем документе.

Пример 2. Сравнение точности картирования чтений между системами, в которых используют гибкое удлинение затравки, и системами, в которых не используют гибкое удлинение затравки

[0205] В данном примере 2 платформу DRAGEN™ использовали для картирования чтений, полученных секвенатором нуклеиновых кислот, эталонной последовательности. Каждая платформа DRAGEN™ картировала один и тот же набор чтений с одной и той же эталонной последовательностью. После завершения картирования компьютерная система определяла точность картирования чтений для каждой операции картирования в зависимости от частоты ошибок картирования.

[0206] Платформа DRAGEN™ представляет собой блок картирования и выравнивания, реализованный в аппаратной схеме с программируемой пользователем вентильной матрицей (FPGA). В платформе DRAGEN™ v7 в настоящее время не используют гибкое удлинение затравки, описанное в настоящем документе, тогда как в платформе DRAGEN™ v8 и платформе DRAGEN™ v8 hi-effort используют гибкое удлинение затравки.

[0207] Xотя платформа DRAGEN™, используемая в настоящем документе, была реализована в виде FPGA, в целом платформа DRAGEN™ может также быть реализована в виде других интегральных схем, таких как специализированная интегральная схема (ASIC).

[0208] Различие между платформами DRAGEN™ v8 и платформами DRAGEN™ v8 hi-effort состоит в настройке эвристики и других параметров. В платформе DRAGEN™ v8 используют следующие эвристические параметры: ориентир-для-интервала=32, максимум-совпадений-интервала=16 и выборка-совпадений-интервала=16. Каждый из этих эвристических параметров описан в настоящем документе. Кроме того, в платформе DRAGEN™ v8 используют другие параметры максимум-вч-совпадений=16, экстренные-вч=0 и св-экстра-интервал=1. Параметр «максимум-вч-совпадений» показывает максимальное число совпадений со случайными выборками, взятых из достигнутых интервалов совпадений перед ошибкой удлинения затравки (например, одна выборка на ошибку удлинения до достижения предела). Параметр «экстренные-вч» определяет, используют ли затратные экстренные операции сканирования для совпадений, найденных только случайными выборками из интервалов совпадений. Экстренные сканирования представляют собой способ поиска возможных парных выравниваний чтений поблизости от потенциальных выравниваний чтений. Параметр «св-экстра-интервал» определяет политику использования затратного выравнивания алгоритмом Смита - Ватермана для совпадений, найденных путем обращения к наилучшему («экстра») интервалу или найденных путем случайной выборки из интервала совпадений. Алгоритм Смита - Ватермана обычно не используют, когда выравнивания без пропусков не обрезаны, но можно использовать, когда выравнивания без пропусков обрезаны, в зависимости от эвристических параметров, включая эту настройку. Настройка «1» означает, что алгоритм Смита - Ватермана можно использовать для кандидатов, полученных из экстра/наилучших интервалов совпадений, к которым получают полный доступ, но не путем случайной выборки. Настройка «2» означает, что алгоритм Смита - Ватермана может также быть использован для кандидатов, полученных из случайной выборки из интервалов совпадений. Настройка «0» будет означать, что алгоритм Смита - Ватермана не применяют к кандидатам, полученным из экстра/наилучших интервалов или при случайной выборке из интервалов совпадений.

[0209] С другой стороны, в платформе DRAGEN™ v8 hi-effort используют следующие эвристические параметры: ориентир-для-интервала=32, максимум-совпадений-интервала=64 и выборка-совпадений-интервала=48. Кроме того, в платформе DRAGEN™ v8 hi-effort используют другие параметры максимум-вч-совпадений=32, экстренные-вч=0 и св-экстра-интервал=2. Соответственно, платформа DRAGEN™ v8 hi-effort имеет более интенсивный набор эвристики, чем платформа DRAGEN™ v8.

[0210] На ФИГ. 8 представлен линейный график 800, отображающий данные результатов тестирования в виде точности картирования чтений в системе, в которой используют способ гибкого удлинения затравки, описанный в настоящем документе, по сравнению с системой, в которой не используют способ гибкого удлинения затравки. В частности, график 800 использует кривую точности в виде кривой (или линии) соотношения правильных и ложных обнаружений (ROC-кривая) для отображения согласования между ложноположительными и ложноотрицательными результатами, когда данные стратифицированы с использованием показателя доверительности. На ФИГ. 8 кривая (или линия), расположенная ближе к верхнему и левому краям графика 800, предполагает более высокую точность картирования чтений.

[0211] Показана кривая 810, отражающая точность картирования чтений для платформы DRAGEN™ v7, в которой не используют гибкое удлинение затравки, как описано в одном или более вариантах осуществления в настоящем документе, в процессе картирования. Показана кривая 820, отражающая точность картирования чтений для платформы DRAGEN™ v8, в которой используют гибкое удлинение затравки, как описано в одном или более вариантах осуществления в настоящем документе, в процессе картирования. Сравнение кривой 810 и кривой 820 показывает, что кривая 820 находится ближе к верхнему и левому краям, чем кривая 810. Таким образом, улучшения точности картирования чтений достигали просто за счет реализации с определенным качеством гибкого удлинения затравки, как описано в одном или более вариантах осуществления в настоящем документе.

[0212] На ФИГ. 8 дополнительно показана кривая 830, которая отражает реализацию платформы DRAGEN™ v8 в варианте hi-effort. Как и в варианте реализации DRAGEN™ v8, в варианте реализации DRAGEN™ v8 hi-effort в процессе картирования также используют способ гибкого удлинения затравки, описанный в настоящем документе. Однако, как описано выше, эвристика, используемая в варианте осуществления DRAGEN™ v8 hi-effort, интенсивнее, чем эвристика, используемая в варианте осуществления DRAGEN™ v8, эффективность которой представлена на кривой 820. Версии DRAGEN™ v8 hi-effort присвоен параметр (например, св-экстра-интервал=2), который увеличивает готовность к выполнению большей дальнейшей работы по выравниванию алгоритмом Смита - Ватермана по сравнению с реализацией DRAGEN™ v8 (например, св-экстра-интервал=1). Как показано на ФИГ. 8, кривая 830 находится ближе к верхней и левой границам, чем обе кривые 810 и 820, что дает значительный прирост эффективности для точности картирования чтений в реализации DRAGEN™ v8 hi-effort.

[0213] На ФИГ. 8 также показана кривая 840, отражающая точность картирования чтений, достигнутую с помощью программного средства картирования BWA-MEM. В программном средстве картирования BWA-MEM используют преобразование эталонного генома алгоритмом Барроуза-Уилера (BWT) в качестве индекса для эталонного генома. Данным способом представления эталонного генома можно по сути обеспечивать преимущества, сходные с преимуществами, предлагаемыми гибким удлинений затравки, например возможность извлечения полного набора совпадений, соответствующего любой длине совпадения. Как показывают кривые 830 и 840, вариант реализации DRAGEN™ v8 hi-effort может обеспечивать ту же точность картирования чтений, что и программный инструмент картирования BWA. Таким образом, для DRAGEN™ v8 hi-effort важно обеспечивать уровень точности картирования чтений, сопоставимый с программным инструментом картирования BWA, поскольку DRAGEN™ v8 hi-effort также имеет другие преимущества платформы DRAGEN™, к которым относятся, например, меньшее количество обращений к памяти для картирования затравок. Однако до реализации основанного на аппаратном обеспечении гибкого удлинения затравки, описанного в настоящем документе, платформа DRAGEN™ могла достичь тех же уровней точности картирования чтений, что и программное средство картирования BWA.

[0214] Таким образом, реализация гибкого удлинения затравки, в котором используют хеш-таблицы, описанные в настоящем документе, позволяет существенно улучшить характеристики в плане точности картирования чтений по сравнению с традиционными способами, в которых не генерируют или не используют хеш-таблицы, описанные в настоящем документе.

ДРУГИЕ ВАРИАНТЫ ОСУЩЕСТВЛЕНИЯ

[0215] Описан ряд вариантов осуществления. Тем не менее будет очевидно, что возможны различные модификации без отклонения от сущности и объема изобретения. Кроме того, логические потоки, изображенные на фигурах, не требуют показанного определенного или последовательного порядка для достижения желаемых результатов. Кроме того, могут быть предусмотрены и другие этапы, или же этапы могут быть исключены из описанных потоков, и в описанные системы могут быть добавлены или удалены из них другие компоненты. Соответственно, нижеследующая формула изобретения охватывает другие варианты осуществления.

Изобретение относится к средствам для создания и использования хеш-таблицы для картирования чтений образца с эталонной последовательностью. Технический результат заключается в повышении эффективности картирования чтений. Получают первую нуклеотидную затравку из эталонной последовательности, причем первая затравка имеет длину в K нуклеотидов. Определяют, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, на основании чего выполняют генерирование дерева удлинения затравки, имеющего множество узлов. Причем каждый узел из множества узлов соответствует удлиненной затравке, которая представляет собой удлинение первой затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и одной или более позициям в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой. 6 н. и 69 з.п. ф-лы, 8 ил.

1. Способ генерирования хеш-таблицы для картирования чтений образца с эталонной последовательностью, включающий:

получение с помощью компьютерной системы первой нуклеотидной затравки из эталонной последовательности, причем первая затравка имеет длину в K нуклеотидов;

определение с помощью компьютерной системы, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности;

на основании определения того, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование с помощью компьютерной системы дерева удлинения затравки, имеющего множество узлов, причем каждый узел из множества узлов соответствует

удлиненной затравке, которая представляет собой удлинение первой затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и

одной или более позициям в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой; и

для каждого узла из множества узлов:

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

2. Способ по п. 1, в котором каждая из совпадающих позиций эталонной последовательности включает в себя K нуклеотидов первой затравки.

3. Способ по п. 1, дополнительно включающий:

получение с помощью компьютерной системы второй нуклеотидной затравки из эталонной последовательности, которая отличается от первой затравки;

определение с помощью компьютерной системы, что вторая затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности; и

на основании определения с помощью компьютерной системы, что вторая затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности:

получение с помощью компьютерной системы данных, описывающих каждую из позиций эталонной последовательности, которая совпадает со второй затравкой; и

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

4. Способ по любому из пп. 1-3, в котором одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, содержат непрерывный интервал позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой.

5. Способ по любому из пп. 1-3, в котором одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, содержат прерывистый интервал в таблице удлинений затравки с позициями эталонной последовательности, которые совпадают с удлиненной затравкой.

6. Способ по любому из пп. 1-5, в котором получение с помощью компьютерной системы первой нуклеотидной затравки из эталонной последовательности, причем первая затравка представляет собой последовательность нуклеотидов, имеющую длину в K нуклеотидов, включает:

определение с помощью компьютерной системы позиции окна доступа к затравке в пределах эталонной последовательности; и

получение с помощью компьютерной системы части эталонной последовательности, идентифицированной окном доступа к затравке.

7. Способ по п. 6, дополнительно включающий:

перемещение с помощью компьютерной системы окна доступа к затравке на К нуклеотидов вперед вдоль эталонной последовательности для идентификации в эталонной последовательности второй нуклеотидной затравки, имеющей длину в K нуклеотидов;

получение с помощью компьютерной системы второй затравки из эталонной последовательности;

определение с помощью компьютерной системы, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности;

на основании определения того, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование с помощью компьютерной системы второго дерева удлинения затравки, имеющего множество вторых узлов, причем каждый второй узел из множества вторых узлов соответствует (i) второй удлиненной затравке, которая представляет собой удлинение второй затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и (ii) второй одной или более позициям во второй таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают со второй удлиненной затравкой; и

для каждого второго узла из множества вторых узлов:

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

8. Способ по любому из пп. 1-7, дополнительно включающий:

для каждого узла из множества узлов:

определение с помощью компьютерной системы, является ли узел дерева удлинения затравки концевым узлом; и

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

9. Способ по п. 8, в котором запись об удлинении включает в себя одну или более команд, при исполнении которых компьютерной системой компьютерная система добавляет один или более дополнительных нуклеотидов к затравке, ассоциированной с записью об удлинении.

10. Способ по п. 8 или 9, дополнительно включающий:

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

11. Способ по любому из пп. 1-7, дополнительно включающий:

генерирование с помощью компьютерной системы таблицы удлинений затравки, включающее:

выявление с помощью компьютерной системы каждой затравки эталонной последовательности, которая совпадает с первой затравкой; и

сохранение с помощью компьютерной системы данных, идентифицирующих выявленные затравки, в таблице удлинений затравки.

12. Способ по п. 11, дополнительно включающий:

сортировку с помощью компьютерной системы выявленных затравок в таблице удлинений затравки.

13. Способ по любому из пп. 1-12, дополнительно включающий:

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

14. Способ по п. 13,

в котором пакет для инсталляции хеш-таблицы включает в себя таблицу удлинений затравки, и

при этом пакет для инсталляции хеш-таблицы включает в себя команды для сохранения (i) программируемой логической схемой или (ii) другим компьютером таблицы удлинений затравки в запоминающем устройстве, доступном для программируемой логической схемы.

15. Способ по любому из п. 13 или 14, дополнительно включающий передачу с помощью компьютерной системы пакета для инсталляции хеш-таблицы на другой компьютер.

16. Способ по п. 15, в котором другой компьютер включает в себя (i) компьютер, выполненный с возможностью обмена данными с программируемой логической схемой, или (ii) программируемую логическую схему.

17. Способ по любому из пп. 1-16, в котором компьютерная система содержит множество компьютеров.

18. Система для генерирования хеш-таблицы для картирования чтений образца с эталонной последовательностью, содержащая:

один или более компьютеров и одно или более устройств хранения, на которых хранятся команды, при исполнении которых одним или более компьютерами один или более компьютеров выполняют операции, включающие:

получение одним или более компьютерами первой нуклеотидной затравки из эталонной последовательности, причем первая затравка имеет длину в K нуклеотидов;

определение одним или более компьютерами, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности;

на основании определения того, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование одним или более компьютерами дерева удлинения затравки, имеющего множество узлов, причем каждый узел из множества узлов соответствует (i) удлиненной затравке, которая представляет собой удлинение первой затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и (ii) одной или более позициям в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой; и

для каждого узла из множества узлов:

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

19. Система по п. 18, в которой каждая из совпадающих позиций эталонной последовательности включает в себя K нуклеотидов первой затравки.

20. Система по п. 18, в которой операции дополнительно включают:

получение одним или более компьютерами второй нуклеотидной затравки из эталонной последовательности, которая отличается от первой затравки;

определение одним или более компьютерами, что вторая затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности; и

на основании определения одним или более компьютерами, что вторая затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности:

получение одним или более компьютерами данных, описывающих каждую из позиций эталонной последовательности, которые совпадают со второй затравкой; и

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

21. Система по любому из пп. 18-20, в которой одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, содержат непрерывный интервал позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой.

22. Система по любому из пп. 18-20, в которой одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, содержат прерывистый интервал в таблице удлинений затравки с позициями эталонной последовательности, которые совпадают с удлиненной затравкой.

23. Система по любому из пп. 18-22, в которой получение одним или более компьютерами первой нуклеотидной затравки из эталонной последовательности, причем первая затравка представляет собой последовательность нуклеотидов, имеющую длину в K нуклеотидов, включает:

определение одним или более компьютерами позиции окна доступа к затравке в пределах эталонной последовательности; и

получение одним или более компьютерами части эталонной последовательности, идентифицируемой окном доступа к затравке.

24. Система по п. 23, в которой операции дополнительно включают:

перемещение одним или более компьютерами окна доступа к затравке на К нуклеотидов вперед вдоль эталонной последовательности для идентификации в эталонной последовательности второй нуклеотидной затравки, имеющей длину в K нуклеотидов;

получение одним или более компьютерами второй затравки из эталонной последовательности;

определение одним или более компьютерами, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности;

на основании определения того, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование одним или более компьютерами второго дерева удлинения затравки, имеющего множество вторых узлов, причем каждый второй узел из множества вторых узлов соответствует (i) второй удлиненной затравке, которая представляет собой удлинение второй затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и (ii) второй одной или более позициям во второй таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают со второй удлиненной затравкой; и

для каждого второго узла из множества вторых узлов:

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

25. Система по любому из пп. 18-24, в которой операции дополнительно включают:

для каждого узла из множества узлов:

определение одним или более компьютерами, является ли узел дерева удлинения затравки концевым узлом; и

на основании определения одним или более компьютерами, что узел дерева удлинений не является концевым узлом, сохранение одним или более компьютерами записи об удлинении в позиции хеш-таблицы, которая соответствует индексному ключу для удлиненной затравки.

26. Система по п. 25, в которой запись об удлинении включает в себя одну или более команд, при исполнении которых одним или более компьютерами один или более компьютеров добавляют один или более дополнительных нуклеотидов к затравке, ассоциированной с записью об удлинении.

27. Система по п. 25 или 26, в которой операции дополнительно включают:

на основании определения одним или более компьютерами, что узел дерева удлинений является концевым узлом, принятие решения одним или более компьютерами не сохранять запись об удлинении в позиции хеш-таблицы, которая соответствует индексному ключу для удлиненной затравки.

28. Система по любому из пп. 18-25, в которой операции дополнительно включают:

генерирование одним или более компьютерами таблицы удлинений затравки, включающее:

выявление одним или более компьютерами каждой затравки эталонной последовательности, которая совпадает с первой затравкой; и

сохранение одним или более компьютерами данных, идентифицирующих выявленные затравки, в таблице удлинений затравки.

29. Система по п. 28, в которой операции дополнительно включают:

сортировку одним или более компьютерами выявленных затравок в таблице удлинений затравки.

30. Система по любому из пп. 18-28, в которой операции дополнительно включают:

генерирование одним или более компьютерами пакета для инсталляции хеш-таблицы, причем пакет для инсталляции хеш-таблицы включает в себя команды, при обработке которых одним или более компьютерами, принявшими пакет для инсталляции хеш-таблицы, один или более компьютеров устанавливают хеш-таблицу в память, доступную для программируемой логической схемы.

31. Система по п. 30,

в которой пакет для инсталляции хеш-таблицы включает в себя таблицу удлинений затравки, и

при этом пакет для инсталляции хеш-таблицы включает в себя команды для сохранения (i) программируемой логической схемой или (ii) другим компьютером таблицы удлинений затравки в запоминающем устройстве, доступном для программируемой логической схемы.

32. Система по п. 30 или 31, в которой операции дополнительно включают:

передачу одним или более компьютерами пакета для инсталляции хеш-таблицы на другой компьютер.

33. Система по п. 32, в которой другой компьютер включает в себя (i) компьютер, выполненный с возможностью обмена данными с программируемой логической схемой, или (ii) программируемую логическую схему.

34. Система по любому из пп. 18-32, в которой один или более компьютеров представляют собой множество компьютеров.

35. Невременный машиночитаемый носитель, на котором хранится программное обеспечение, содержащее команды, выполненные с возможностью исполнения одним или более компьютерами, при исполнении которых один или более компьютеров выполняют операции, включающие:

получение одним или более компьютерами первой нуклеотидной затравки из эталонной последовательности, причем первая затравка имеет длину в K нуклеотидов;

определение одним или более компьютерами, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности;

на основании определения того, что первая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование одним или более компьютерами дерева удлинения затравки, имеющего множество узлов, причем каждый узел из множества узлов соответствует (i) удлиненной затравке, которая представляет собой удлинение первой затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и (ii) одной или более позициям в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой; и

для каждого узла из множества узлов:

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

36. Машиночитаемый носитель по п. 35, в котором каждая из совпадающих позиций эталонной последовательности включает в себя K нуклеотидов первой затравки.

37. Машиночитаемый носитель по п. 35, в котором операции дополнительно включают:

получение одним или более компьютерами второй нуклеотидной затравки из эталонной последовательности, которая отличается от первой затравки;

определение одним или более компьютерами, что вторая затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности; и

на основании определения одним или более компьютерами, что вторая затравка не имеет превышающего заданное число количества совпадений с позициями эталонной последовательности:

получение одним или более компьютерами данных, описывающих каждую из позиций эталонной последовательности, которые совпадают со второй затравкой; и

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

38. Машиночитаемый носитель по любому из пп. 35-37, в котором одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, содержат непрерывный интервал позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой.

39. Машиночитаемый носитель по любому из пп. 35-37, в котором одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с удлиненной затравкой, содержат прерывистый интервал в таблице удлинений затравки с позициями эталонной последовательности, которые совпадают с удлиненной затравкой.

40. Машиночитаемый носитель по любому из пп. 35-39, в котором получение одним или более компьютерами первой нуклеотидной затравки из эталонной последовательности, причем первая затравка представляет собой последовательность нуклеотидов, имеющую длину в K нуклеотидов, включает:

определение одним или более компьютерами позиции окна доступа к затравке в пределах эталонной последовательности; и

получение одним или более компьютерами части эталонной последовательности, идентифицируемой окном доступа к затравке.

41. Машиночитаемый носитель по п. 40, в котором операции дополнительно включают:

перемещение одним или более компьютерами окна доступа к затравке на К нуклеотидов вперед вдоль эталонной последовательности для идентификации в эталонной последовательности второй нуклеотидной затравки, имеющей длину в K нуклеотидов;

получение одним или более компьютерами второй затравки из эталонной последовательности;

определение одним или более компьютерами, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности;

на основании определения того, что вторая затравка имеет превышающее заданное число количество совпадений с позициями эталонной последовательности, генерирование одним или более компьютерами второго дерева удлинения затравки, имеющего множество вторых узлов, причем каждый второй узел из множества вторых узлов соответствует (i) второй удлиненной затравке, которая представляет собой удлинение второй затравки и имеет длину в K* нуклеотидов, причем K* на один или более нуклеотидов больше, чем K, и (ii) второй одной или более позициям во второй таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают со второй удлиненной затравкой; и

для каждого второго узла из множества вторых узлов:

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

42. Машиночитаемый носитель по любому из пп. 35-41, в котором операции дополнительно включают:

для каждого узла из множества узлов:

определение одним или более компьютерами, является ли узел дерева удлинения затравки концевым узлом; и

на основании определения одним или более компьютерами, что узел дерева удлинений не является концевым узлом, сохранение одним или более компьютерами записи об удлинении в позиции хеш-таблицы, которая соответствует индексному ключу для удлиненной затравки.

43. Машиночитаемый носитель по п. 42, в котором запись об удлинении включает в себя одну или более команд, при исполнении которых одним или более компьютерами один или более компьютеров добавляют один или более дополнительных нуклеотидов к затравке, ассоциированной с записью об удлинении.

44. Машиночитаемый носитель по п. 42 или 43, в котором операции дополнительно включают:

на основании определения одним или более компьютерами, что узел дерева удлинений является концевым узлом, принятие решения одним или более компьютерами не сохранять запись об удлинении в позиции хеш-таблицы, которая соответствует индексному ключу для удлиненной затравки.

45. Машиночитаемый носитель по любому из пп. 35-42, в котором операции дополнительно включают:

генерирование одним или более компьютерами таблицы удлинений затравки, включающее:

выявление одним или более компьютерами каждой затравки эталонной последовательности, которая совпадает с первой затравкой; и

сохранение одним или более компьютерами данных, идентифицирующих выявленные затравки, в таблице удлинений затравки.

46. Машиночитаемый носитель по п. 45, в котором операции дополнительно включают:

сортировку одним или более компьютерами выявленных затравок в таблице удлинений затравки.

47. Машиночитаемый носитель по любому из пп. 35-45, в котором операции дополнительно включают:

генерирование одним или более компьютерами пакета для инсталляции хеш-таблицы, причем пакет для инсталляции хеш-таблицы включает в себя команды, при обработке которых одним или более компьютерами, принявшими пакет для инсталляции хеш-таблицы, один или более компьютеров устанавливают хеш-таблицу в память, доступную для программируемой логической схемы.

48. Машиночитаемый носитель по п. 47,

в котором пакет для инсталляции хеш-таблицы включает в себя таблицу удлинений затравки, и

при этом пакет для инсталляции хеш-таблицы включает в себя команды для сохранения (i) программируемой логической схемой или (ii) другим компьютером таблицы удлинений затравки в запоминающем устройстве, доступном для программируемой логической схемы.

49. Машиночитаемый носитель по п. 47 или 48, в котором операции дополнительно включают:

передачу одним или более компьютерами пакета для инсталляции хеш-таблицы на другой компьютер.

50. Машиночитаемый носитель по п. 49, в котором другой компьютер включает в себя (i) компьютер, выполненный с возможностью обмена данными с программируемой логической схемой, или (ii) программируемую логическую схему.

51. Машиночитаемый носитель по любому из пп. 35-50, в котором один или более компьютеров представляют собой множество компьютеров.

52. Способ применения хеш-таблицы для картирования чтений образца с эталонной последовательностью, включающий:

выполнение блоком картирования и выравнивания запроса к хеш-таблице, причем запрос включает в себя первую затравку, при этом первая затравка включает в себя подгруппу нуклеотидов, которые были получены из конкретного чтения из чтений образца;

получение блоком картирования и выравнивания ответа на выполненный запрос, который включает в себя информацию, хранящуюся в позиции хеш-таблицы, которая определяется как ответ на запрос;

определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности;

на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены (i) запись об удлинении и (ii) запись об интервале:

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

на основании определения, что доступ к таблице удлинений не нужен:

определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал;

генерирование блоком картирования и выравнивания первой удлиненной затравки, которая представляет собой удлинение первой затравки с использованием записи об удлинении;

генерирование блоком картирования и выравнивания последующего хеш-запроса, который включает в себя первую удлиненную затравку; и

выполнение блоком картирования и выравнивания последующего запроса к хеш-таблице.

53. Способ по п. 52, дополнительно включающий:

на основании определения, что доступ к таблице удлинений нужен:

доступ блоком картирования и выравнивания к таблице удлинений для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается запись об интервале; и

добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

54. Способ по п. 52 или 53, дополнительно включающий:

определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос одна или более совпадающих позиций эталонной последовательности; и

на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены одна или более совпадающих позиций эталонной последовательности:

добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

55. Способ по любому из пп. 52-54, в котором определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал, включает:

определение блоком картирования и выравнивания отсутствия предыдущей информации, описывающей запись об интервале в качестве потенциального наилучшего интервала для конкретного чтения; и

сохранение блоком картирования и выравнивания первой информации, описывающей запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал.

56. Способ по любому из пп. 52-55, дополнительно включающий:

получение блоком картирования и выравнивания ответа на последующий выполненный запрос, который включает в себя информацию, хранящуюся в позиции хеш-таблицы, которая определяется как ответ на запрос;

определение блоком картирования и выравнивания, включены ли в ответ на последующий выполненный запрос (i) вторая запись об удлинении, (ii) вторая запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности;

на основании определения блоком картирования и выравнивания, что в ответ на последующий выполненный запрос включены (i) вторая запись об удлинении и (ii) вторая запись об интервале:

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

на основании определения, что доступ к таблице удлинений не нужен:

определение блоком картирования и выравнивания с использованием одного или более эвристических правил, использовать ли вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала;

генерирование блоком картирования и выравнивания второй удлиненной затравки, которая представляет собой удлинение первой удлиненной затравки с использованием второй записи об удлинении;

генерирование блоком картирования и выравнивания третьего хеш-запроса, который включает в себя вторую удлиненную затравку; и

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

57. Способ по п. 56, в котором определение блоком картирования и выравнивания с использованием одного или более эвристических правил, использовать ли вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала, включает:

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

58. Способ по любому из пп. 52-57, в котором запись об интервале ссылается на одну или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с первой затравкой из запроса.

59. Способ по п. 58, в котором одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с первой затравкой из запроса, содержат:

непрерывный интервал в таблице удлинений из позиций эталонной последовательности, которые совпадают с первой затравкой из запроса.

60. Система для применения хеш-таблицы для улучшения картирования чтений образца эталонной последовательности, содержащая:

один или более компьютеров и одно или более устройств хранения, на которых хранятся команды, при исполнении которых одним или более компьютерами один или более компьютеров выполняют операции, включающие:

выполнение блоком картирования и выравнивания запроса к хеш-таблице, причем запрос включает в себя первую затравку, при этом первая затравка включает в себя подгруппу нуклеотидов, которые были получены из конкретного чтения из чтений образца;

получение блоком картирования и выравнивания ответа на выполненный запрос, который включает в себя информацию, хранящуюся в позиции хеш-таблицы, которая определяется как ответ на запрос;

определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности;

на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены (i) запись об удлинении и (ii) запись об интервале:

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

на основании определения, что доступ к таблице удлинений не нужен:

определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал;

генерирование блоком картирования и выравнивания первой удлиненной затравки, которая представляет собой удлинение первой затравки с использованием записи об удлинении;

генерирование блоком картирования и выравнивания последующего хеш-запроса, который включает в себя первую удлиненную затравку; и

выполнение блоком картирования и выравнивания последующего хеш-запроса к хеш-таблице.

61. Система по п. 60, в которой операции дополнительно включают:

на основании определения, что доступ к таблице удлинений нужен:

доступ блоком картирования и выравнивания к таблице удлинений для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается запись об интервале; и

добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

62. Система по п. 60 или 61, в которой операции дополнительно включают:

определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос одна или более совпадающих позиций эталонной последовательности; и

на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены одна или более совпадающих позиций эталонной последовательности:

добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

63. Система по любому из пп. 60-62, в которой определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал, включает:

определение блоком картирования и выравнивания отсутствия предыдущей информации, описывающей запись об интервале в качестве потенциального наилучшего интервала для конкретного чтения; и

сохранение блоком картирования и выравнивания первой информации, описывающей запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал.

64. Система по любому из пп. 60-63, в которой операции дополнительно включают:

получение блоком картирования и выравнивания ответа на последующий выполненный запрос, который включает в себя информацию, хранящуюся в позиции хеш-таблицы, которая определяется как ответ на запрос;

определение блоком картирования и выравнивания, включены ли в ответ на последующий выполненный запрос (i) вторая запись об удлинении, (ii) вторая запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности;

на основании определения блоком картирования и выравнивания, что в ответ на последующий выполненный запрос включены (i) вторая запись об удлинении и (ii) вторая запись об интервале:

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

на основании определения, что доступ к таблице удлинений не нужен:

определение блоком картирования и выравнивания с использованием одного или более эвристических правил, использовать ли вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала;

генерирование блоком картирования и выравнивания второй удлиненной затравки, которая представляет собой удлинение первой удлиненной затравки с использованием второй записи об удлинении;

генерирование блоком картирования и выравнивания третьего хеш-запроса, который включает в себя вторую удлиненную затравку; и

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

65. Система по п. 64, в которой определение блоком картирования и выравнивания с использованием одного или более эвристических правил, использовать ли вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала, включает:

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

66. Система по любому из пп. 60-65, в которой запись об интервале ссылается на одну или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с первой затравкой из запроса.

67. Система по п. 66, в которой одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с первой затравкой из запроса, содержат:

непрерывный интервал в таблице удлинений из позиций эталонной последовательности, которые совпадают с первой затравкой из запроса.

68. Невременный машиночитаемый носитель, на котором хранится программное обеспечение, содержащее команды, выполненные с возможностью исполнения одним или более компьютерами, при исполнении которых один или более компьютеров выполняют операции, включающие:

выполнение блоком картирования и выравнивания запроса к хеш-таблице, причем запрос включает в себя первую затравку, при этом первая затравка включает в себя подгруппу нуклеотидов, которые были получены из конкретного чтения из чтений образца;

получение блоком картирования и выравнивания ответа на выполненный запрос, который включает в себя информацию, хранящуюся в позиции хеш-таблицы, которая определяется как ответ на запрос;

определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос (i) запись об удлинении, (ii) запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности;

на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены (i) запись об удлинении и (ii) запись об интервале:

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

на основании определения, что доступ к таблице удлинений не нужен:

определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал;

генерирование блоком картирования и выравнивания первой удлиненной затравки, которая представляет собой удлинение первой затравки с использованием записи об удлинении;

генерирование блоком картирования и выравнивания последующего хеш-запроса, который включает в себя первую удлиненную затравку; и

выполнение блоком картирования и выравнивания последующего запроса к хеш-таблице.

69. Машиночитаемый носитель по п. 68, в котором операции дополнительно включают:

на основании определения, что доступ к таблице удлинений нужен:

доступ блоком картирования и выравнивания к таблице удлинений для получения одной или более совпадающих позиций эталонной последовательности в таблице удлинений, на которые ссылается запись об интервале; и

добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

70. Машиночитаемый носитель по п. 68 или 69, в котором операции дополнительно включают:

определение блоком картирования и выравнивания, включены ли в ответ на выполненный запрос одна или более совпадающих позиций эталонной последовательности; и

на основании определения блоком картирования и выравнивания, что в ответ на выполненный запрос включены одна или более совпадающих позиций эталонной последовательности:

добавление блоком картирования и выравнивания одной или более совпадающих позиций эталонной последовательности к набору совпадений с затравкой.

71. Машиночитаемый носитель по любому из пп. 68-70, в котором определение блоком картирования и выравнивания, нужно ли хранить первую информацию, описывающую запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал, включает:

определение блоком картирования и выравнивания отсутствия предыдущей информации, описывающей запись об интервале в качестве потенциального наилучшего интервала для конкретного чтения; и

сохранение блоком картирования и выравнивания первой информации, описывающей запись об интервале, в запоминающем устройстве в качестве информации, описывающей потенциальный наилучший интервал.

72. Машиночитаемый носитель по любому из пп. 68-71, в котором операции дополнительно включают:

получение блоком картирования и выравнивания ответа на последующий выполненный запрос, который включает в себя информацию, хранящуюся в позиции хеш-таблицы, которая определяется как ответ на запрос;

определение блоком картирования и выравнивания, включены ли в ответ на последующий выполненный запрос (i) вторая запись об удлинении, (ii) вторая запись об интервале или (iii) одна или более совпадающих позиций эталонной последовательности;

на основании определения блоком картирования и выравнивания, что в ответ на последующий выполненный запрос включены (i) вторая запись об удлинении и (ii) вторая запись об интервале:

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

на основании определения, что доступ к таблице удлинений не нужен:

определение блоком картирования и выравнивания с использованием одного или более эвристических правил, использовать ли вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала;

генерирование блоком картирования и выравнивания второй удлиненной затравки, которая представляет собой удлинение первой удлиненной затравки с использованием второй записи об удлинении;

генерирование блоком картирования и выравнивания третьего хеш-запроса, который включает в себя вторую удлиненную затравку; и

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

73. Машиночитаемый носитель по п. 72, в котором определение блоком картирования и выравнивания с использованием одного или более эвристических правил, использовать ли вторую информацию, описывающую вторую запись об интервале, или первую информацию, описывающую потенциальный наилучший интервал, в качестве потенциального наилучшего интервала, включает:

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

74. Машиночитаемый носитель по любому из пп. 68-73, в котором запись об интервале ссылается на одну или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с первой затравкой из запроса.

75. Машиночитаемый носитель по п. 74, в котором одна или более позиций в таблице удлинений затравки, которые включают в себя данные, описывающие позиции эталонной последовательности, которые совпадают с первой затравкой из запроса, содержат:

непрерывный интервал в таблице удлинений из позиций эталонной последовательности, которые совпадают с первой затравкой из запроса.