АППАРАТНО-УСКОРЕННОЕ ГЕНЕРИРОВАНИЕ K-МЕРНОГО ГРАФА Российский патент 2024 года по МПК G16B30/20 G16B20/20 

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

[0001] Данная заявка испрашивает преимущество по предварительной заявке на патент США №63/006 668, поданной 7 апреля 2020 г., которая полностью включена в настоящий документ путем ссылки.

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

[0002] Для представления множества секвенирующих считываний можно использовать K-мерные графы.

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

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

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

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

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

[0007] В некоторых вариантах реализации устройство управления реализовано с использованием одного или более ЦП или ГП для выполнения программных команд для реализации функций устройства управления.

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

[0009] В некоторых вариантах реализации программные команды могут исполняться одним или более ЦП или ГП для реализации одной или более функций блока распознавания вариантов.

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

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

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

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

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

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

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

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

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

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

[0020] Другие варианты осуществления могут включать в себя способы и системы, выполненные с возможностью осуществления работы аппаратных схем аппаратного-ускоренного блока генерирования графов.

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

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

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

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

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

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

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

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

[0029] В некоторых вариантах реализации вторая аппаратная логика дополнительно выполнена с возможностью: присвоения краевой массы каждому краю K-мерного графа.

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

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

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

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

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

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

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

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

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

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

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

[0041] В некоторых вариантах реализации вторая аппаратная логика дополнительно выполнена с возможностью: присвоения краевой массы каждому краю K-мерного графа.

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

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

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

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

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

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

[0048] Другие варианты осуществления могут включать в себя способы и системы, выполненные с возможностью осуществления работы аппаратных схем аппаратного-ускоренного блока генерирования графов.

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

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

[0051] В некоторых вариантах реализации вторая аппаратная логика дополнительно выполнена с возможностью: присвоения краевой массы каждому краю K-мерного графа.

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

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

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

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

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

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

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

[0058] На ФИГ. 1 представлен пример системы для аппаратно-ускоренного генерирования K-мерного графа.

[0059] На ФИГ. 2 представлена структурная схема примера способа аппаратно-ускоренного генерирования K-мерного графа.

[0060] На ФИГ. 3 представлена структурная схема другого примера способа аппаратно-ускоренного генерирования K-мерного графа.

[0061] На ФИГ. 4 представлен пример K-мерного графа.

[0062] На ФИГ. 5 представлена блок-схема примера компонентов системы, которые могут быть использованы для аппаратно-ускоренного K-мерного графа.

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

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

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

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

[0066] На ФИГ. 1 представлен пример системы 100 для аппаратно-ускоренного генерирования K-мерного графа. В некоторых вариантах реализации система 100 может включать в себя секвенатор 110 нуклеиновых кислот, базу данных 120 эталонных последовательностей, аппаратно-ускоренный блок 130 генерирования графов, множество аппаратных логических блоков 131, 132, 133, 134, 135, 136, 137, 138, устройство управления 140, буферную емкость 150 хеш-таблицы, DRAM 160 и блок распознавания вариантов 180. В некоторых вариантах реализации аппаратно-ускоренный блок 130 генерирования графов может быть реализован с использованием программируемой логической схемы, такой как программируемая пользователем вентильная матрица (FPGA). В других вариантах реализации аппаратно-ускоренный блок 130 генерирования графов может быть реализован с использованием специализированной схемы (ASIC). В любом сценарии функциональные возможности, описанные в отношении аппаратно-ускоренного блока 130 генерирования графов и каждого из компонентов, реализованных на нем, реализованы с использованием логических схем аппаратного обеспечения, выполненных с возможностью реализации функциональных возможностей, описанных в настоящем документе, без выполнения программных команд для реализации функциональных возможностей.

[0067] В настоящем описании термин «блок» используется для описания программного модуля, аппаратного модуля или их комбинации, которая используется для выполнения указанной функции. Определение того, является ли конкретный «блок», описанный в настоящем документе, аппаратным, программным или их комбинацией, может быть выполнено на основании контекста его использования. Например, «блок ввода» 131, «блок графического узла» 132, «краевой блок графа» 133 и т.п., в аппаратно-ускоренном блоке 130 генерирования графов, который реализован с использованием FPGA или ASIC, представляет собой аппаратный блок, функциональные возможности которого реализованы с помощью аппаратных цифровых логических элементов или аппаратных цифровых логических блоков, которые размещены с возможностью реализации функциональных возможностей, описанных в настоящем документе в отношении конкретного «блока». В качестве другого примера «блок 180 распознавания вариантов», который не реализован с использованием аппаратно-ускоренного блока 130 генерирования графов, представленного на ФИГ. 1, представляет собой программный модуль, функциональность которого реализована одним или более компьютерами, исполняющими программные команды, определяющие функциональность «блока 180 распознавания вариантов». В качестве другого примера компьютер или блок обработки может представлять собой аппаратное устройство, реализующее функциональные возможности путем обработки программных команд, и, таким образом, функциональные возможности компьютера или блока обработки представляют собой комбинацию аппаратного и программного обеспечения.

[0068] Хотя примеры одного или более компонентов, показанных на ФИГ. 1, представлены в настоящем документе в виде аппаратных реализаций, таких как «устройство управления» 140, поскольку «устройство управления» показано на ФИГ. 1 как реализованное в аппаратно-ускоренном блоке 130 генерирования графов, настоящее описание не ограничено такими примерами. Вместо этого можно использовать другие варианты реализации, в которых «устройство управления » 140 реализовано в программном обеспечении в виде программного модуля или комбинации аппаратного и программного обеспечения с компьютером или блоком обработки данных, исполняющим программные команды для реализации функционала описанного в настоящем документе «устройства управления» 140. Аналогичным образом, возможны варианты реализации настоящего описания, в которых определенные компоненты, описанные как программное обеспечение со ссылкой на ФИГ. 1, такие как «блок 180 распознавания вариантов», реализованы в виде аппаратной реализации.

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

[0070] Таким образом, каждое считывание представляет собой данные, которые представляют собой часть генома нуклеиновой кислоты для организма, такого как животное, насекомое, растение и т.п. Предполагая, что короткие фрагменты нуклеотидной последовательности имеют приблизительно 600 распознаваний оснований, первое считывание может представлять собой 150 упорядоченных нуклеотидов для первого конца фрагмента нуклеотидной последовательности, а второе считывание может представлять собой 150 упорядоченных нуклеотидов другого конца фрагмента нуклеотидной последовательности. Однако эти числа являются лишь примерами, и любой секвенатор 110 нуклеиновых кислот может быть выполнен с возможностью генерирования считываний, которые могут выполняться аппаратно-ускоренным блоком генерирования графов, как описано в настоящем документе, с использованием любых способов секвенирования. Такие считывания могут иметь длину, отличную от значений длины, упомянутых в настоящем документе. Например, в некоторых вариантах реализации настоящее описание можно использовать для генерирования аппаратно-ускоренных K-мерных графов для считываний, полученных фрагментами нуклеотидной последовательности, имеющими до 1000 нуклеотидов или более, причем каждое считывание имеет, например, 50 распознавания оснований, 75 распознавания оснований, 150 распознавания оснований, 200 распознавания оснований, 300 распознавания оснований, 500 распознавания оснований или более с конца каждого фрагмента. Каждое распознавание оснований может соответствовать нуклеотиду. Настоящее описание также можно использовать для построения аппаратно-ускоренных K-мерных графов для длинных считываний. Соответственно, аппаратно-ускоренный блок 130 генерирования графов можно использовать для генерирования K-мерных графов для любых считываний, сгенерированных любым способом любым типом секвенатора нуклеиновых кислот.[0071] В некоторых вариантах реализации биологический образец 105 может включать образец ДНК, а секвенатор 110 нуклеиновых кислот может включать секвенатор ДНК. В таких вариантах реализации порядок секвенированных нуклеотидов в считывании, полученном секвенатором нуклеиновых кислот, может включать один или более из гуанина (Г), цитозина (Ц), аденина (А) и тимина (Т) в любой комбинации. В некоторых вариантах реализации секвенатор 110 нуклеиновых кислот можно использовать для секвенирования образцов РНК. В некоторых вариантах реализации это может происходить с использованием протоколов RNA-seq. В качестве примера, образец РНК может быть предварительно обработан с применением обратной транскрипции с образованием комплементарной ДНК (кДНК) с помощью фермента обратной транскриптазы. В других вариантах реализации секвенатор 110 нуклеиновых кислот может включать секвенатор РНК, а биологический образец может включать образец РНК. Соответственно, хотя в примере, показанном на ФИГ. 1, описан секвенатор нуклеиновых кислот, который производит считывания, состоящие из Г, Ц, А и Т, генерируемых секвенатором ДНК на основе образца ДНК, настоящее описание не ограничено этим. Вместо этого в других вариантах осуществления процесс может обрабатывать считывания, состоящие из Ц, Г, А и У, которые получены секвенатором РНК на основе образца РНК. В некоторых вариантах осуществления считывания ДНК или считывания РНК, полученные секвенатором нуклеиновых кислот, могут включать в себя распознавание оснований N, причем N указывает на распознавание неизвестных оснований, сгенерированное секвенатором нуклеиновых кислот.

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

[0073] Секвенатор 110 нуклеиновых кислот может получать эталонный геном 122 из базы данных 122 эталонных геномов. В некоторых вариантах реализации получают только часть эталонного генома 122. Полученная часть эталонного генома 122 может соответствовать эталонным местоположениям эталонного генома 122, с которыми сопоставляют и приводят в соответствие набор считываний 112. База данных 122 данных эталонных геномов может включать в себя хранилище данных, которое организует хранение множества различных эталонных геномов. В некоторых вариантах реализации конкретный эталонный геном 122, выбранный из базы данных эталонных геномов, может быть основан на типе образца 105 ДНК. В некоторых вариантах осуществления тип выбранного эталонного генома 122, выбранного из базы 120 эталонного генома, может быть выбран на основании входных данных от пользователя секвенатора 110 нуклеиновых кислот. В таких вариантах реализации пользователь может, например, выбрать идентификатор эталонного генома 120, который может использоваться секвенатором 110 нуклеиновых кислот для выбора конкретного эталонного генома 122 из базы 120 эталонных геномов. Эталонный геном 122 может включать в себя, например, нуклеотидную последовательность, собранную в качестве репрезентативного примера набора генов для конкретного вида.

[0074] Комбинация набора считываний 112, сгенерированных секвенатором 110 нуклеиновых кислот, и полученного эталонного генома 122 может быть предоставлена в качестве входных данных для аппаратно-ускоренного блока 130 генерирования графов. Эти входные данные могут обрабатываться одним или более аппаратными логическими блоками 131-138 аппаратно-ускоренного блока 130 генерирования графов для генерирования экземпляра K-мерного графа. Например, каждый аппаратный логический блок из аппаратных логических блоков 131-138 может быть конфигурирован с возможностью выполнения соответствующих операций для каждого считывания из набора считываний 112, включенных в качестве входных данных для аппаратно-ускоренного блока 130 генерирования графов.

[0075] В настоящем документе описана система 100, показанная на ФИГ. 1, включающая секвенатор нуклеиновых кислот. В некоторых вариантах реализации, таких как описанные со ссылкой на ФИГ. 1, система может включать в себя секвенатор 110, аппаратно-ускоренный блок 130 генерирования графов, а другие компоненты системы 100 могут быть интегрированы в секвенатор 110 нуклеиновых кислот. Однако настоящее описание не ограничено интеграцией в секвенатор 110 нуклеиновых кислот. Вместо этого в некоторых вариантах реализации аппаратно-ускоренный блок 130 генерирования графов может быть реализован в программируемом логическом устройстве или ASIC, интегрированном или размещенном в компьютере, удаленном от секвенатора 110 нуклеиновых кислот и соединенном с возможностью связи со секвенатором 110 нуклеиновых кислот, например, с помощью одной или более проводных или беспроводных сетей. Аналогичным образом база данных 120, блок 180 распознавания вариантов или и то, и другое могут быть реализованы за пределами секвенатора нуклеиновых кислот. 110. Аналогичным образом, нет необходимости в том, чтобы система 100 вообще включала секвенатор 110 нуклеиновых кислот. Вместо этого в некоторых вариантах реализации аппаратно-ускоренный блок 130 генерирования графов и другие компоненты, показанные на ФИГ. 1, могут быть реализованы в компьютерной системе, которая не включает в себя секвенатор 110 нуклеиновых кислот. В таких вариантах реализации аппаратно-ускоренный блок генерирования графов может получать набор считываний 112, эталонной последовательности 122 или обеих посредством сети из места (мест) хранения одного или более запоминающих устройств или т.п. Соответственно, система 100 изображает пример настоящего описания, но не ограничивает настоящее описание какой-либо конкретной конфигурацией компонентов системы.

[0076] Один или более аппаратных логических блоков аппаратно-ускоренного блока 130 генерирования графов могут включать в себя блок 131 ввода, блок 132 узла графа, краевой блок 133 графа, блок 134 обратного распространения сигнала, циклический блок 135, блок 136 отсечения, блок 137 вывода графа и блок 138 уничтожения. В некоторых вариантах реализации генерирование K-мерного графа с помощью аппаратно-ускоренного блока 130 генерирования графов может включать в себя устройство 140 управления, активирующее и конфигурирующее каждый из аппаратных логических блоков 131-138 для выполнения соответствующих аппаратных логических операций по набору данных, хранящихся в буферной емкости 150 или DRAM 160. В других вариантах реализации устройство 140 управления может активировать и конфигурировать только подмножество аппаратных логических блоков 131-138 для выполнения их соответствующей аппаратной логической операции на наборе исходных графических данных, хранящихся в буферной емкости 150 или DRAM 160.

[0077] В качестве примера в некоторых вариантах реализации аппаратно-ускоренный блок 130 генерирования графов можно использовать для генерирования специализированной формы графа де Брёйна. Эту специализированную форму графа де Брёйна можно оптимизировать таким образом, чтобы на графе представляли неуникальные K-меры с использованием множества соответствующих узлов, каждый из которых имеет один край, а не представляли одним узлом с множеством краев. Это может быть частично достигнуто с помощью графического блока 132 для идентификации неуникальных K-меров и маркировки неуникальных K-меров для дальнейшей обработки. Неуникальный K-мер может быть определен как последовательность K-меров, которая возникает по меньшей мере в два раза в любом одном считывании или по меньшей мере два раза в эталонной последовательности. Уникальный K-мер в одном и том же

считывании возникает не более одного раза, но все еще может возникать при множестве считываний.

[0078] Однако в других вариантах реализации можно создавать графы де Брёйна без различения уникальных или неуникальных K-меров. Таким образом, в некоторых вариантах реализации блок 132 узла графа, который может идентифицировать неуникальные K-меры, необязательно должен быть реализован. В еще одном примере блок 134 обратного распространения сигнала не обязательно использовать для генерирования всех K-мерных графов. Вместо этого блок 134 обратного распространения сигнала может быть ограничен вариантами реализации, в которых он может улучшать производительность. В качестве примера блок 134 обратного распространения сигнала можно использовать для повышения качества краевых масс при будущем преобразовании сгенерированного K-мерного графа в граф последовательности.

[0079] Пример генерирования K-мерного графа, описанный в отношении примера, показанного на ФИГ. 1, показывает каждый аппаратный логический блок 131-138, который может быть активирован и сконфигурирован устройством 140 управления. В настоящем описании каждый аппаратный логический блок 131-138 по существу описан как активированный устройством 140 управления, сконфигурированный устройством 140 управления с использованием, например, данных, описывающих граф, хранящихся в устройстве 140 управления, с получением исходных графов, с выполнением одной или более конкретных операций обработки полученных исходных графов или других данных и с последующим обновлением исходных графов, данных описания графов или обоих вариантов осуществления настоящего изобретения, не имеет таких ограничений. Вместе с тем настоящее описание не ограничивается такими вариантами реализации. Вместо этого в некоторых вариантах реализации каждый аппаратный логический блок 131-138 может быть выполнен с возможностью исполнения множества экземпляров соответствующих им функциональных возможностей. Например, блок 132 узла графа может быть выполнен с возможностью приема до 3 отдельных наборов исходных графических данных и одновременного выполнения их операций на нем, логический блок 135 аппаратного обеспечения цикла может быть выполнен с возможностью принятия до 3 отдельных наборов исходных графических данных и одновременного выполнения на нем операций, а PRU может быть выполнен с возможностью принятия до 2 отдельных наборов исходных графических данных и одновременного выполнения на нем операций. Количество отдельных наборов или исходных графических данных, каждое из которых соответствует различным K-мерным графам, может быть принято и обработано конкретным аппаратным логическим блоком 131-138, ограничено только доступными аппаратными ресурсами для системы 100. Например, предполагая, что для использования доступны достаточные уровни логических единиц DRAM и FPGA, число отдельных наборов исходных графических данных, которые могут быть получены и одновременно обработаны логическими блоками аппаратного обеспечения 131-138, может быть более 3. Аналогичным образом, один или более аппаратных логических блоков 131-138 могут быть выполнены с возможностью приема и одновременной обработки меньшего количества наборов исходных графических данных, если такие ресурсы недоступны или если ожидается, что конкретный аппаратный логический блок не будет в значительной степени использован.

[0080] В других вариантах реализации не требуется только один экземпляр каждого аппаратного логического блока 131-138, каждый из которых выполнен с возможностью одновременной обработки отдельных наборов исходных графических данных, каждый из которых соответствует разным K-мерным графам. Вместо этого в некоторых вариантах реализации множество экземпляров каждого аппаратно-ускоренного блока 130 генерирования графов может быть выполнено с возможностью включения множества экземпляров одного или более аппаратных логических блоков 131-138. В таких случаях устройство 140 управления может быть выполнено с возможностью отслеживания состояния и доступности каждого аппаратного логического блока 131-138, а затем активации и конфигурирования каждого аппаратного логического блока таким образом, чтобы уравновешивать операции обработки при нагрузке на каждый соответствующий аппаратный логический блок. Например, в некоторых вариантах реализации аппаратно-ускоренный блок 130 генерирования графов может быть выполнен с возможностью наличия 3 экземпляров блока 132 узла графа, каждый из которых выполнен с возможностью приема до 3 отдельных наборов исходных графических данных и одновременного выполнения их операций с ними, 3 экземпляра краевого блока 133 графа, каждый из которых выполнен с возможностью приема до 3 отдельных наборов исходных графических данных и одновременного выполнения их операций с ними, 2 блока 134 обратного распространения сигнала, каждый из которых выполнен с возможностью приема до 2 отдельных наборов исходных графических данных и одновременного выполнения своих операций на них, и 3 циклических блока 135, каждый из которых выполнен с возможностью приема до 2 отдельных наборов исходных графических данных и одновременного выполнения своих операций на них. Активация/деактивация каждого аппаратного логического блока, конфигурация каждого аппаратного логического блока, входные данные для каждого аппаратного логического блока, выходные данные из каждого аппаратного логического блока и обновление данных описания графа каждым аппаратным логическим блоком управляются и направляются устройством 140 управления.

[0081] Блок ввода

[0082] Блок 131 ввода может принимать входные данные, которые включают сгенерированный набор считываний 112 и выбранный эталонный геном 122, которые в настоящем документе могут называться исходными графическими данными. Выбранный эталонный геном 122 может включать в себя участок эталонного генома. Исходные графические данные могут включать в себя, например, данные, обрабатываемые одним или более аппаратными логическими блоками 131-138 во время генерирования экземпляра K-мерного графа. Хотя исходные графические данные включают в себя, например, сгенерированные считывания 112 и выбранный эталонный геном 122, исходные графические данные также могут включать в себя, например, K-мерные узлы, сгенерированные блоком 132 узла графа, края, сгенерированные краевым блоком 133 графа, и т.п. Блок 131 ввода может форматировать сгенерированные считывания 112 и полученный эталонный геном 122 для хранения в DRAM 160. Форматирование сгенерированных считываний может включать в себя, например, кодирование считываний для хранения в DRAM 160. В некоторых вариантах реализации кодирование считывания может включать кодирование каждого распознавания оснований, соответствующего нуклеотиду считывания, в 4-битные значения. Например, А может быть закодировано как 0000, Ц может быть закодировано как 0001, Г может быть закодирован как 0010, Т может быть закодировано как 0011, а N может быть закодировано как 0100, где N представляет собой распознавание неизвестного основания. В некоторых вариантах реализации кодированные данные также могут включать в себя данные, которые представляют собой показатель MAPQ, число считываний, длину последовательности, метки SAM, распознавания оснований или нуклеотиды считывания, один или более индикаторов качества считывания, отличных от показателя MAPQ, или любую их комбинацию. Кодированные считанные данные могут находиться в диапазоне от 16-битного значения до 64-битного значения или более, которое описывает считанное значение. Блок 131 ввода может записывать генерируемые считывания на DRAM 160.

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

[0084] Инициализация данных описания графа может включать в себя, например, генерирование устройством 140 управления идентификатора K-мерного графа для исходных входных данных, генерирование структуры данных информации о состоянии графа или их комбинацию. Идентификатор K-мерного графа включает в себя строку данных из одного или более символов, одного или более чисел или их комбинацию, которая может быть использована для идентификации экземпляра K-мерного графа в ходе процесса генерирования K-мерного графа с момента приема исходных графических данных блоком 131 ввода до по меньшей мере момента использования блока 138 уничтожения для удаления данных, относящихся к идентификатору K-мерного графа, из буферной емкости 150, DRAM 160 или обоих вариантов после полного создания K-мерного графа для конкретного набора исходных графических данных. В некоторых вариантах реализации идентификатор K-мерного графа может включать в себя число, такое как 6-битное число, имеющее значение в диапазоне 0-63. В некоторых вариантах реализации идентификатор K-мерного графа можно даже использовать для ссылки на K-мерный граф после использования блока уничтожения для удаления вышеупомянутых данных из буферной емкости 150, DRAM 160 или обоих. Структура данных с информацией о состоянии графа представляет собой структуру данных, имеющую одно или более полей, которые хранят данные, описывающие текущее состояние экземпляра K-мерного графа, который должен быть сгенерирован для конкретного набора исходных входных данных. Информация о состоянии может включать в себя, например, данные, указывающие на последнюю логику аппаратного обеспечения, которая работает на исходных графах для конкретного случая K-мерного графа, данные, указывающие, прекратил ли последний блок логики аппаратного обеспечения операцию, данные, указывающие длину K-мера, данные, указывающие список узлов K-мера, данные, указывающие список указателей, которые могут быть использованы для идентификации узлов K-мера в буферной емкости, длину списка узлов K-мера, данные, включающие список неуникальных K-меров, данные, указывающие местоположения исходных входных данных в буферной емкости или DRAM, данные, указывающие базовый адрес в DRAM для узлов экземпляра K-мерного графа, или любое их подмножество или комбинацию.

[0085] Блок 131 ввода может форматировать входные считывания 112 и эталонный геном 122 и записывать входные считывания 112 и эталонный геном в DRAM 160. Устройство 140 управления может определять, когда блок 131 ввода завершил форматирование и запись входных считываний 112 и эталонного генома 122 в DRAM 160. После обнаружения устройством управления 140 завершения форматирования и записи входных считываний 112 и эталонного генома 122 в DRAM устройство управления 140 может обновить информацию о состоянии графа для указания того, что блок ввода 131 завершил операции по первым исходным графическим данным для первого экземпляра K-мерного графа.

[0086] После того как первые исходные графические данные были введены, отформатированы и сохранены в DRAM 160, устройство управления 140 может определить следующую аппаратную логическую единицу, которая должна быть активирована и сконфигурирована далее. Например, устройство 140 управления может активировать и конфигурировать блок 132 узла графа для генерирования K-мерных узлов на основании части эталонного генома 122 и набора считываний, сформатированных и сохраненных в DRAM 160.

[0087] Блок узла графа

[0088] Устройство 140 управления может активировать и конфигурировать блок 132 узла графа для продолжения генерирования первого экземпляра K-мерного графа путем обработки форматированных считываний 112 и эталонного генома 122, хранящихся в DRAM. Это может включать в себя, например, отправку сигнала управления на блок 132 узла графа, предоставление данных описания графа на блок 132 узла графа или их комбинацию. Данные описания графов могут использоваться для конфигурирования блока 132 узла графа для работы. Например, предоставление данных описания графа блоку 132 узла графа и от устройства 140 управления может привести к конфигурированию блока 132 узла графа для идентификации K-меров определенного размера, который определен данными описания графа. Аналогичным образом для конфигурирования аппаратного логического блока, такого как блок 132 узла графа, можно использовать другие поля данных описания графа, описанных в настоящем документе.

[0089] Кроме того, по существу параллельно устройство 140 управления может обнаруживать, что блок 131 ввода принял вторые исходные графические данные в качестве входных данных. Затем устройство 140 управления может активировать блок 131 ввода, дать блоку 131 указание форматировать считывания и эталонный геном вторых исходных графических данных и генерировать вторые графические данные описания для второго экземпляра K-мерного графа, который должен быть сгенерирован на основе вторых исходных графических данных. Таким образом, управляющее устройство 140 может обеспечивать высокие уровни пропускной способности путем одновременного управления рабочими характеристиками различных аппаратных логических блоков 131, 132, которые выполняют процессы генерирования K-мерного графа для различных наборов исходных графических данных на разных стадиях обработки. Устройство управления 140 выполнено с возможностью управления этой параллельной функцией каждого из аппаратных логических блоков 131, 132, 133, 134, 135, 136, 137, 138, например, в любой конкретный момент времени может быть восемь аппаратных логических блоков, которые работают с восемью различными наборами исходных графических данных, причем аппаратно-ускоренный блок 130 генерирования графов работает с возможностью одновременного генерирования восьми разных K-мерных графов. Устройство управления 140, использующее данные графического описания, управляет этим процессом в течение всего времени путем активации и конфигурирования каждого соответствующего аппаратного логического блока для достижения абстрактно высокоуровневых конвейерных функциональных возможностей неконвейерных аппаратных логических блоков 131, 132, 133, 134, 135, 136, 137, 138, которые не имеют прямого и физического соединения ввода/вывода между каждым соответствующим аппаратным логическим блоком. Хотя проиллюстрирован пример восьми одновременных генерирований K-мерных графов, выполняемых одновременно, настоящее описание может быть выполнено с возможностью достижения гораздо большего числа одновременных генерирований K-мерных графов, например, путем реализации множества аппаратно-ускоренных графов 130 одновременно, множества экземпляров множества аппаратных логических блоков на одном или более аппаратно-ускоренных блоках 130 генерирования графа или их комбинации.

[0090] Блок 132 узла графа может анализировать каждое считывание набора считываний 112 для идентификации каждого из K-меров считывания. Это может включать в себя, например, скольжение окна доступа к K-меру вдоль каждого положения каждого считывания для идентификации каждого конкретного K-мера соответствующего считывания. Блок 132 узла графа может хранить данные, представляющие узел K-мерного графа для каждого идентифицированного K-мера каждого считывания, в буферной емкости 150. Аналогичным образом, блок 132 узла графа также может генерировать и сохранять в DRAM список указателей узла в структуре данных указателей узла, причем каждый указатель узла указывает на местоположение буферной емкости в K-мерном узле. Блок 132 узла графа также может генерировать и хранить информацию, указывающую местоположение и длину списка узлов для каждого K-мерного графа в данных описания графа, хранимых устройством управления. Эти указатели могут использоваться в качестве информации о состоянии графа устройством 140 управления для конфигурирования другого аппаратного логического блока во время последующей части процесса генерирования K-мерного графа. Буферная емкость 150 может использовать одну или более политик когерентности буферной емкости, таких как политика когерентности буферной емкости LRU, выполненная с возможностью воспользоваться самыми старыми объектами буферной емкости 150, причем самые старые объекты определяют на основании времени записи объекта в буферную емкость 150.

[0091] Пример данных, сгенерированных блоком 132 узла графа и хранящихся в буферной емкости 150, DRAM 160 или в обоих, показан со ссылкой на ФИГ. 4. На ФИГ. 4 представлена часть эталонного генома 410, считывание 420 и граф 400 де Брёйна. Граф де Брёйна 400, который более подробно описан ниже, включает в себя узел для каждого K-мера в участке генома 410 и считывание 420 и край между каждой парой K-мерных узлов, соединяющий пару узлов, имеющих k-1 перекрывающихся нуклеотидов.

[0092] Как показано в примере на ФИГ. 4, блок 132 узла графа может генерировать на основе приема части эталонного генома 410 и считывания 420 данные, представляющие узлы 431, 432, 433, 434, 435, 436, 437, 438 первого пути 430 графа де Брёйна 400 и узлы 441, 442, 443, 444. Сначала блок 132 узла графа может выравнивать перекрывающиеся участки эталонного генома 410а, 410b и перекрывающиеся участки считывания 420а, 420b для идентификации перекрывающихся участков, как показано на ФИГ. 4. Блок 132 узла графа может идентифицировать каждый из K-меров участка генома 410 и считывания 420. Этого можно достичь с помощью окна доступа длиной к, которое равно 4 в данном примере, в первом положении участка эталонного генома 410, захватывающего K-мер, идентифицированный окном доступа, генерирования данных, представляющих узел графа, который включает в себя захваченный K-мер, сохранения данных, представляющих узел, в буферной емкости 150, продвижение окна доступа на один нуклеотид, а затем итерационное повторение этого процесса. В данном примере блок графического узла 132 может идентифицировать K-меры АТЦГ, ТЦГЦ, ЦГССС, ГЦЦТ, ЦЦТА, ЦТАГ, ТАГА и АГААА для участка эталонного генома 410 и генерировать соответствующий узел 431, 432, 433, 434, 435, 436, 437, 438, причем один из этих узлов соответствует соответствующему K-меру. Каждый узел создан таким образом, что он имеет длину k, которая в данном примере составляет 4, и имеет число перекрывающихся k-1 K-меров со следующим соседним узлом. Блок 132 узла графа может сохранять сгенерированные узлы в буферной емкости 150, DRAM 160 или в обоих. В некоторых вариантах осуществления буферная емкость может включать в себя буферную емкость хеш-таблицы. В таких вариантах реализации узлы могут храниться в виде ключей хеш-таблицы. Блок 132 узла графа может хранить данные, описывающие местоположения K-мерных узлов в данных описания графа, хранимых устройством 140 управления.

[0093] Блок 132 узла графа может выполнять те же операции для считывания 420. Что касается считывания 420, блок 132 узла графа может идентифицировать K-меры АТЦГ, ТЦГС, ЦГСГ, ГЦГТ, ЦГТА, ГТАГ, ТАГА и АГАА. Аналогичным образом этого можно достичь с помощью окна доступа длиной к, которая в данном примере равна 4, в первом положении части считывания 420, захватывающего K-мер, идентифицированный окном доступа, а затем продвигающего окно доступа и повторяющего процесс. Блок 132 узла графа может начинаться с идентификации каждого K-мера для участка генома 410. В некоторых вариантах реализации блок 132 узла графа может генерировать соответствующий узел для каждого из K-меров. В других вариантах реализации блок 132 узла графа может генерировать только 431, 432, 433, 434, 435, 436, 437, 438, соответствующие идентифицированным K-мерам, которые отличаются от K-мерных узлов участка эталонного генома 410. В каждом сценарии каждый узел создан таким образом, что он имеет длину k, которая в данном примере составляет 4, и имеет число перекрывающихся k-1 K-меров со следующим соседним узлом. Это может продолжаться до тех пор, пока узел для каждого K-мера участка эталонного генома 410 не будет создан и сохранен в буферной емкости 150 или DRAM 160.

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

[0095] На этом этапе процесса блок 132 узла графа сохраняет данные, представляющие узел K-мерного графа для каждого K-мера в буферной емкости 150, DRAM 160 или в обоих. Таким образом, аппаратно-ускоренный блок 130 генерирования графов еще не сгенерировал края 431а, 432а 433а, 434а, 435а, 436а, 437а, 432b, 441а, 442а, 443а, 444а, массы краев графа или т.п. Эти признаки данного экземпляра K-мерного графа могут быть сгенерированы с помощью одного или более других аппаратных логических блоков аппаратно-ускоренного блока 130 генерирования графов.

[0096] Устройство 140 управления может отслеживать работу блока 132 узла графа. После того как блок 132 узла графа генерирует данные, представляющие узел K-мера для каждого K-мера каждого считывания первых исходных графических данных для этого первого экземпляра K-мерного графа, устройство управления может обновлять данные описания графа для указания того, что аппаратно-ускоренный блок 130 генерирования графов завершил операции блока 132 графа на первых исходных графических данных. Кроме того, в устройстве 140 управления также могут храниться данные описания графов, которые включают в себя, например, метку, идентифицирующую каждый из неуникальных K-меров, местоположения хранения для узлов K-мерных графов и данные, указывающие на завершение операций блоком 132 узла графа.

[0097] После генерирования и сохранения в буферной емкости 150 узлов K-мерного графа устройство 140 управления может определять следующий аппаратный логический блок, который должен быть активирован и сконфигурирован далее. Например, устройство 140 управления может активировать и конфигурировать краевой блок 133 графа для генерирования, взвешивания или и того, и другого краев графа между парами узлов.

[0098] Краевой блок графа

[0099] Краевой блок 133 графа может генерировать края графа между парами K-мерных узлов, сгенерированных блоком 132 узла графа. Устройство 140 управления может активировать краевой блок 133 графа после определения того, что блок 132 узла графа для первого экземпляра K-мерного графа завершен и что краевой блок 133 графа доступен. В некоторых вариантах реализации устройство 140 управления может предоставлять или иным образом обеспечивать доступ к местоположениям краевого блока 133 графа, хранящим узлы K-мерного графа, сгенерированные блоком 132 узла графа, для конкретного экземпляра K-мерного графа. Например, устройство 140 управления может получать доступ к данным описания K-мерного графа, сгенерированным и сохраненным блоком 132 узла графа в процессе генерирования K-мерных узлов для экземпляра K-мерного графа. Доступные данные о K-мерном графе могут указывать или иным образом описывать список K-меров.

[000100] После получения краевым блоком 133 графа местоположения узлов K-мерного графа для первого экземпляра K-мерного графа краевой блок графа может начинать генерировать один или более краев графа между данными, представляющими K-мерные узлы. В некоторых вариантах реализации краевой блок 133 графа может получать доступ к данным, представляющим узел графа, для каждого из K-меров конкретного считывания из буферной емкости хеш-таблицы. Краевой блок 133 графа может генерировать для хранения в буферной емкости хеш-таблицы данные, представляющие край графа между узлами графов для K-меров. Например, данные, представляющие край графа, могут храниться в буферной емкости хеш-таблицы как часть записи узла графа для исходного узла края. В некоторых вариантах реализации краевой блок 133 графа может присваивать массу каждому краю K-мерного графа. Например, краевой блок 133 графа может добавлять +1 или другую массу для каждого случая края графа, соединяющего соответствующую пару K-меров.

[000101] В качестве примера краевой блок 133 графа может идентифицировать узлы с помощью данных описания графа, полученных от устройства 140 управления, которые являются соседними узлами. Узлы могут быть определены как соседние узлы на основании различных факторов, включая определение того, что узлы совместно используют k-1 перекрывающихся нуклеотидов и что узлы наблюдаются в двух последовательных положениях скользящего окна доступа к K-меру. Например, краевой блок 133 графа может перемещать окно доступа к K-меру вдоль каждого положения каждого считывания исходных графических данных. В некоторых вариантах реализации краевой блок 133 графа может создавать край или увеличивать краевую массу при определении того, что в считывании наблюдаются два последовательных K-мера, перекрывающихся всем, кроме одного основания. Узел 133 графа создает край или увеличивает краевую массу в таком сценарии, поскольку этот сценарий подразумевает край между узлами графа, соответствующими этим двум последовательным K-мерам.

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

[000103] Как показано в примере на ФИГ. 4, краевой блок 133 графа может генерировать данные, представляющие один или более краев между парами узлов 431, 432, 433, 434, 435, 436, 437, 438 первого пути 430, парами узлов 441, 442, 443, 444 второго пути 440 или одну или более пар узлов в первом пути 430 и втором пути 440. Пример этих краев показан на ФИГ. 4 в виде краев 431а, 432а, 433а, 434а, 435а, 436а, 437а, 432b, 441а, 442а, 443а, 444а.

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

[000105] Блок обратного распространения сигнала

[000106] Аппаратно-ускоренный блок 130 генерирования графов может включать в себя блок 134 обратного распространения сигнала. Однако в определенных вариантах реализации устройство 140 управления может активировать и конфигурировать только блок 134 обратного распространения сигнала. Например, устройство 140 управления может активировать блок 134 обратного распространения сигнала, когда устройство 140 управления определяет, что K-мерный граф, генерируемый текущим набором исходных графов, будет впоследствии преобразован в граф последовательности. При активации модуль 134 обратного распространения сигнала может принимать данные описания графа от устройства 140 управления. В таком варианте реализации корректировки краевых масс графа могут сделать массы более надежными при наследовании графом последовательности.

[000107] Краевой блок графа 133 может создавать края между узлами K-меров контигов путем идентификации соответствующих узлов K-меров в буферной емкости 150, формирования края, соединяющего узлы K-меров, а затем увеличения краевой массы +1 для каждого случая. В некоторых вариантах реализации после добавления к графу K-меров узлов контига и взвешивания с использованием краевого блока 134 графа блок 134 обратного распространения сигнала можно использовать для обратного распространения сигнала +1 инкремент краевой массы k-1 через линейную цепь краев графа «слева» начального узла контига в K-мерном графе. В этом контексте «слева» от начального узла контига в K-мерном графе представляет собой направление K-мерного графа, противоположное направленному краю K-мерного графа. Для иллюстрации этой концепции «слева» узла 434 на графе 400 де Брёйна будет являться узлами 433, 432 и 431.

[000108] Например, в некоторых вариантах реализации модуль 134 обратного распространения сигнала может получать доступ в буферной емкости хеш-таблицы, к данным, представляющим K-мерный граф, включая его K-мерные узлы, соответствующие края графа или т.п., а затем корректировать краевые массы для узлов K-1, которые возникают до начала нового контига. Блок 135 обратного распространения может определять соответствующие K-мерные узлы и края для корректировки на основании данных описания графа, принятых от устройства 160 управления, которое включает в себя указатели для местоположений буферной емкости, хранящих эту информацию. Данные описания графа могут обновляться при любых изменениях, которые происходят во время обратного распространения сигнала.

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

[000110] Циклический блок

[000111] Аппаратно-ускоренный блок 130 генерирования графов может включать в себя циклический блок 135. В некоторых вариантах реализации циклический блок 135 может быть активирован и настроен устройством 140 управления для обнаружения циклов в случае K-мерного графа. Например, циклический блок 135 может оценивать K-мерные узлы и K-мерные края исходных графических данных экземпляра K-мерного графа, сгенерированного одним или более из блока 131 ввода, блока 132 узла графа, краевого блока 133 графа и блока 134 обратного распространения сигнала. Циклический блок 135 выполнен с возможностью приема данных описания графа от устройства 140 управления. Циклический блок 135 может итерационно помечать узлы шапки для удаления. Верхний узел может включать в себя узел, который не включает в себя каких-либо внутренних краев. Где внутренний край представляет собой край, который направлен от первого узла к самому первому узлу. После того как каждый узел шапки помечен для удаления, циклический блок 135 может определять, станут ли какие-либо узлы, которые направлены к наружному краю, узлами шапки в результате удаления узла. Если определены такие узлы, они помечены для удаления. Наружный край представляет собой край графа, который указывает от первого узла к другому узлу. Циклический блок 135 может продолжать выполнение этого процесса до тех пор, пока не останется узлов шапки.

[000112] После определения того, что узлов шапки не остались, циклический блок 135 может определить, является ли граф пустым, причем пустой граф означает, что все узлы графа помечены для удаления. Если граф без шапки пуст, то цикл отсутствовал. Альтернативно, если граф без шапки не пустой, то граф должен содержать цикл. Циклы устойчивы к удалению такого типа, поскольку ни один узел в цикле не становится узлом шапки путем удаления узлов за пределами цикла.

[000113] После выполнения любого из этих определений циклический блок 135 может предоставить устройству 140 управления указание того, был ли обнаружен цикл. Затем, на основании указания, предоставленного циклическим блоком 135, устройство 140 управления может определить, какой аппаратный логический блок следует затем активировать и конфигурировать. Например, если был обнаружен цикл и необходимо прервать генерирование экземпляра K-мерного графа, то устройство 140 управления может активировать и конфигурировать блок 138 уничтожения. В таких случаях блок уничтожения может удалять необработанные графические данные из буферной емкости 150 и DRAM 160, соответствующие экземпляру прерванного K-мерного графа. Если в альтернативном варианте осуществления необходимо продолжить генерирование экземпляра K-мерного графа, то устройство 140 управления может активировать и конфигурировать другой аппаратный логический блок для выполнения последующих операций по исходным графическим данным для генерирования экземпляра K-мерного графа. Например, если необходимо продолжить генерирование K-мерного графа, устройство 140 управления может либо активировать, либо конфигурировать блок 136 отсечения, либо блок 137 вывода графа.

[000114] Хотя аппаратно-ускоренный блок 130 генерирования графов может использовать циклический блок 135 для обнаружения циклов в случае генерируемого K-мерного графа, циклический блок 135 может быть избирательно активирован и выполнен аналогично блоку 134 обратного распространения сигнала. Это связано с тем, что некоторые виды K-мерных графов могут включать циклы. Однако для определенных типов K-мерных графов может быть полезно не иметь графов с циклами. Соответственно, аппаратно-ускоренный блок 130 генерирования графов может быть выполнен, например, с возможностью приема входных данных от устройства 140 управления, указывающих, следует ли выполнять циклический блок 135 для конкретного экземпляра графа.

[000115] Блок отсечения

[000116] Аппаратно-ускоренный блок 130 генерирования графов может включать в себя блок 135 отсечения. Подобно блоку 134 обратного распространения сигнала и циклическому блоку 135 блок 136 отсечения может быть избирательно активирован и конфигурирован устройством 160 управления. При активации и конфигурировании блок 135 отсечения может оценивать массу каждого края графа в исходных графических данных для экземпляра K-мерного графа, сгенерированного в этот момент аппаратно-ускоренным блоком 130 генерирования графов. В некоторых вариантах реализации, если блок 136 отсечения определяет, что массовое значение края графа не удовлетворяет заданному пороговому значению, блок 136 отсечения может удалять край графа и любой K-мерный узел, который возникает после идентифицированных краев графа. Альтернативно, если блок 136 отсечения определяет, что массовое значение края графа удовлетворяет заданному пороговому значению, то блок 136 отсечения оставит край графа нетронутым.

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

[000118] Блок вывода графа

[000119] Аппаратно-ускоренный блок 130 генерирования графов может включать в себя блок 137 вывода графа. Блок 137 вывода графа может использоваться аппаратно-ускоренным блоком 130 генерирования графов для генерирования конечной версии 170 экземпляра K-мерного графа, поскольку экземпляр K-мерного графа описан данными графа и буферной емкости. Например, блок 137 вывода графа может получать данные, представляющие K-мерный граф, из буферной емкости 150 хеш-таблицы с использованием данных описания графа, которые включают в себя, например, указатели местоположения в буферной емкости хеш-таблицы, в которых хранятся данные K-мерного графа. Затем блок 137 вывода графа может передавать данные, полученные из буферной емкости 150 хеш-таблицы, описывающей конечную версию K-мерного графа 170, в блок 180 распознавания вариантов. Блок 180 распознавания вариантов может выполнять анализ распознавания вариантов на конечной версии K-мерного графа 170 для создания набора вариантов 190. Набор вариантов 190 может включать один или более потенциальных вариантов. Вариант представляет собой изменение геномных данных организма. Потенциальный вариант представляет собой определение по блоку распознавания вариантов, который логически выводится блоком распознавания вариантов на основе обработки K-мерного графа 170. В некоторых вариантах реализации потенциальный вариант может иметь пороговый уровень ошибки при определении варианта.

[000120] Блок 180 распознавания вариантов может идентифицировать потенциальные варианты путем обработки K-мерного графа 180. В некоторых вариантах реализации, например, блок 180 распознавания вариантов может идентифицировать потенциальный вариант, когда распознавание оснований или нуклеотид одного или более считываний в наборе считываний и нуклеотид эталонного генома отличаются в конкретном местоположении эталонного генома. Данные, описывающие набор вариантов 190, можно генерировать или определить любым количеством способов. Например, в некоторых вариантах реализации могут выполняться операции распознавания вариантов, как более подробно описано, например, в публикации США №2016/0180019, публикации США №2016/0306922 и публикации США №2019/-0259468, содержание каждой из которых полностью включено в настоящий документ путем ссылки. Данные, описывающие набор вариантов 190, могут быть предоставлены для вывода несколькими различными способами. Например, данные, описывающие набор вариантов 190, могут отображаться на дисплее секвенатора 110 нуклеиновых кислот, отображаться на дисплее другого компьютера, выводиться в виде аудио посредством одного или более динамиков вычислительного устройства, выводиться посредством принтера или на любой их комбинации.

[000121] Блок уничтожения

[000122] Блок 138 уничтожения можно использовать для выполнения задач по восстановлению памяти по завершении и вывода экземпляра K-мерного графа аппаратно-ускоренным блоком 130 генерирования графов. Например, блок уничтожения может удалять все исходные графические данные, относящиеся к конкретному экземпляру K-мерного графа, который завершен и выводится аппаратно-ускоренным блоком 130 генерирования графов. В альтернативном или дополнительном варианте осуществления блок 138 уничтожения может удалять все данные, относящиеся к конкретному экземпляру графического блока 130, которые хранятся устройством управления, удалять все данные, относящиеся к конкретному экземпляру графического блока 130, которые хранятся в DRAM 160, или т.п. Соответственно, блок 138 уничтожения может избирательно удалять данные, представляющие узлы графов, и данные, представляющие края K-мерного графа, из буферной емкости хеш-таблицы. Такое удаление является избирательным, поскольку необходимо удалить только часть содержимого буферной емкости, устройства управления или DRAM. Более того, когда граф хранится в виде хеш-таблицы, хеш-таблица часто может быть мало заполнена, и для блока 138 уничтожения быстрее происходит избирательное уничтожение только занятых записей хеш-таблицы, чем очистка всей хеш-таблицы, что приводит к повышению производительности.

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

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

[000125] На ФИГ. 3 представлена структурная схема другого примера способа 300 аппаратно-ускоренного генерирования K-мерного графа. Как правило, процесс 300 может включать в себя получение первого набора нуклеотидных последовательностей, причем первый набор нуклеотидных последовательностей включает в себя (i) множество считываний, соответствующих активной области эталонной последовательности, и (ii) часть эталонной последовательности (310) для каждой конкретной нуклеотидной последовательности из первого набора нуклеотидных последовательностей: генерирование для хранения в буферной емкости хеш-таблицы и первым аппаратным логическим блоком данных, представляющих узел графа для каждого K-мера конкретной нуклеотидной последовательности (320), обнаружение устройством управления того, что первый аппаратный логический блок завершил генерирование узла графа для каждого K-мера конкретной нуклеотидной последовательности (330), конфигурирование устройством управления второго аппаратного логического блока для выполнения генерирования краев графа для сгенерированных узлов графа (340) и для одной или более пар сгенерированных графов узлов: генерирование вторыми аппаратными логическими блоками и для хранения в хеш-таблице графов, данные, представляющие границы графа между одной или более парами сгенерированных узлов графа, сгенерированных первым аппаратным логическим блоком, причем данные, представляющие узел графа для каждого K-мера, хранящиеся в буферной емкости хеш-таблицы, и данные, представляющие края графа, хранящиеся в буферной емкости хеш-таблицы, представляют собой граф K-мера первого набора нуклеотидных последовательностей (350).

[000126] На ФИГ. 4 представлен пример K-мерного графа 400. В данном примере K-мерный граф представляет собой граф 400, генерируемый на основе по меньшей мере части эталонного генома 410 и считывания 420. В данном примере K-мерный граф 400 представляет собой граф де Брёйна.

[000127] K-мерный граф 400 генерируется с использованием множества узлов и одного или более краев между парами узлов. Каждый узел представляет K-мер длиной k, причем в данном примере k=4. Каждый край обеспечивает указание на наличие перекрытия k-1 нуклеотидов K-меров, связанных краем. На K-мерном графе 400 путь 430 включает в себя множество узлов и ребер, представляющих каждый K-мер участка эталонной последовательности 410. Также путь 440 включает в себя множество узлов и ребер, представляющих участки считывания 420, которые отличаются от участка эталонного генома 410.

[000128] На ФИГ. 5 представлена блок-схема примера компонентов системы 500, которые могут быть использованы для аппаратно-ускоренного K-мерного графа.

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

[000130] Вычислительное устройство 500 включает процессор 502, память 504, устройство 506 хранения, высокоскоростной интерфейс 508, соединяющийся с памятью 504 и высокоскоростными расширительными портами 510, и низкоскоростной интерфейс 512, соединяющийся с низкоскоростной шиной 514 и устройством 506 хранения. Все компоненты 502, 504, 506, 508, 510 и 512 соединены друг с другом с помощью различных шин, и могут быть установлены на общей материнской плате или при необходимости другими способами. Процессор 502 может обрабатывать команды, предназначенные для выполнения в вычислительном устройстве 500, включая команды, хранящиеся в запоминающем устройстве 504 или на устройстве 506 хранения, для отображения графической информации графического пользовательского интерфейса на внешнем устройстве ввода/вывода, таком как дисплей 516, соединенный с высокоскоростным интерфейсом 508. В других вариантах реализации при необходимости можно использовать множество процессоров и/или множество шин вместе с множеством запоминающих устройств и типов памяти. Кроме того, множество вычислительных устройств 500 могут быть соединены, причем каждое устройство обеспечивает участок необходимых операций, например это может быть банк серверов, группа блейд-серверов или многопроцессорная система.

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

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

[000133] Высокоскоростной контроллер 508 управляет операциями с большой пропускной способностью для вычислительного устройства 500, а низкоскоростной контроллер 512 управляет операциями с меньшей пропускной способностью. Такое распределение функций является лишь примером. В одном варианте реализации высокоскоростной контроллер 508 соединен с памятью 504, дисплеем 516, например, через графический процессор или ускоритель, и с высокоскоростными расширительными портами 510, в которые можно устанавливать различные платы расширения (не показаны). В варианте реализации низкоскоростной контроллер 512 соединен с устройством 506 хранения и низкоскоростным расширительным портом 514. Низкоскоростной расширительный порт, который может включать различные коммуникационные порты, например USB, Bluetooth, Ethernet, беспроводной Ethernet, может быть соединен с одним или более устройствами ввода/вывода, такими как клавиатура, указательное устройство, пара микрофон/динамик, сканер или сетевое устройство, такое как коммутатор или маршрутизатор, например, с помощью сетевого адаптера. Вычислительное устройство 500 может быть реализовано в нескольких различных формах, как показано на фигуре. Например, оно может быть реализовано как стандартный сервер 520 или многократно, в виде группы таких серверов. Оно может также быть реализовано как часть стоечной серверной системы 524. Кроме того, оно может быть реализовано на персональном компьютере, таком как ноутбук 522. В альтернативном варианте осуществления компоненты вычислительного устройства 500 могут быть объединены с другими компонентами в мобильном устройстве (не показано), таком как устройство 550. Каждое из таких устройств может содержать одно или более вычислительных устройств 500, 550, и вся система может состоять из множества вычислительных устройств 500, 550, взаимодействующих друге другом.

[000134] Вычислительное устройство 500 может быть реализовано в нескольких различных формах, как показано на фигуре. Например, оно может быть реализовано как стандартный сервер 520 или многократно, в виде группы таких серверов. Оно может также быть реализовано как часть стоечной серверной системы 524. Кроме того, оно может быть реализовано на персональном компьютере, таком как ноутбук 522. В альтернативном варианте осуществления компоненты вычислительного устройства 500 могут быть объединены с другими компонентами в мобильном устройстве (не показано), таком как устройство 550. Каждое из таких устройств может содержать одно или более вычислительных устройств 500, 550, и вся система может состоять из множества вычислительных устройств 500, 550, взаимодействующих друге другом.

[000135] Вычислительное устройство 550 включает процессор 552, память 564 и устройство ввода/вывода, такое как, помимо прочего, дисплей 554, коммуникационный интерфейс 566 и приемопередатчик 568. Устройство 550 может также быть снабжено устройством хранения, таким как микропривод или другое устройство, для обеспечения дополнительной возможности хранения. Все компоненты 550, 552, 564, 554, 566 и 568 соединяют друг с другом с помощью различных шин, и некоторые из компонентов могут быть установлены на общей материнской плате или иными способами, в зависимости от ситуации.

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

[000137] Процессор 552 может обмениваться данными с пользователем через интерфейс 558 управления и интерфейс 556 дисплея, соединенный с дисплеем 554. Дисплей 554 может представлять собой, например, дисплей типа TFT (жидкокристаллический дисплей на тонкопленочных транзисторах) или типа OLED (на органических светоизлучающих диодах), или другие подходящие технологии отображения. Интерфейс 556 дисплея может содержать соответствующую схему для приведения дисплея 554 в действие и для представления графической и другой информации пользователю. Интерфейс 558 управления может принимать команды от пользователя и преобразовывать их для передачи процессору 552. Кроме того, может быть предусмотрен внешний интерфейс 562, сообщающийся с процессором 552 для обеспечения устройства 550 связью ближнего радиуса действия с другими устройствами. В некоторых вариантах реализации внешний интерфейс 562 может обеспечивать, например, проводную связь, или в других вариантах реализации беспроводную связь, и можно также использовать множество интерфейсов.

[000138] Информация в запоминающем устройстве 564 хранится в вычислительном устройстве 550. Запоминающее устройство 564 может быть реализована в виде одного или более машиночитаемых носителей или носителей, блока или блоков энергозависимой памяти, или блока или блоков энергонезависимой памяти. Кроме того, может быть предусмотрена расширительная память 574, соединенная с устройством 550 посредством расширительного интерфейса 572, который может включать, например, интерфейс карты SIMM (модуль с однорядным расположением микросхем памяти). Такая расширительная память 574 может обеспечивать устройство 550 дополнительным пространством хранения или может также хранить приложения или другую информацию для устройства 550. В частности, расширительная память 574 может включать команды для выполнения или для дополнения описанных выше процессов, а может также включать защищенную информацию. Таким образом, например, расширительная память 574 может быть обеспечена в качестве защищенного модуля для устройства 550 и может быть запрограммирована командами, которые позволяют использовать устройство 550 защищенным образом. Кроме того, с помощью плат SIMM можно передавать безопасные приложения, а также дополнительную информацию, например размещать идентификационную информацию на карте SIMM без возможности компрометации.

[000139] Память может включать, например, флэш-память и/или память NVRAM, как описано ниже. В одном варианте реализации компьютерный программный продукт на практике реализован на носителе информации. Компьютерный программный продукт содержит команды, при исполнении которых осуществляется один или более способов, такие как описанные выше. Информационный носитель представляет собой компьютерочитаемый или машиночитаемый носитель, такой как запоминающее устройство 564, расширительная память 574 или память на процессоре 552, причем информация может быть принята, например, посредством приемопередатчика 568 или внешнего интерфейса 562.

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

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

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

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

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

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

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

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

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

Изобретение относится к способам и системам аппаратно-ускоренного генерирования K-мерных графов, представляющих множество ридов секвенирования для анализа распознавания вариантов. Технический результат заключается в ускорении генерирования K-мерного графа, что приводит к ускорению процесса геномного анализа в целом. В одном аспекте способ включает действия по получению первого набора нуклеотидных последовательностей, генерируемых секвенатором нуклеиновых кислот, построению K-мерного графа с использованием полученного первого набора нуклеотидных последовательностей и с использованием множества неконвейерных аппаратных логических блоков программируемого логического устройства, и периодическое обновление с помощью устройства управления данными графического представления для K-мерного графа после выполнения одной или более операций каждым аппаратным логическим блоком. 4 н. и 30 з.п. ф-лы, 5 ил.

1. Способ аппаратно-ускоренного генерирования K-мерного графа, представляющего множество ридов секвенирования для анализа распознавания вариантов, включающий:

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

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

в процессе генерирования K-мерного графа:

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

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

3. Способ по п. 1, в котором устройство управления реализовано с использованием аппаратного логического блока программируемого логического устройства.

4. Способ по п. 1, в котором устройство управления реализовано с использованием одного или более ЦП или ГП для выполнения программных команд для реализации функций устройства управления.

5. Способ по п. 1, в котором операции дополнительно включают:

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

6. Способ по п. 5, в котором программные команды исполняются одним или более ЦП или ГП для реализации одной или более функций блока распознавания вариантов.

7. Способ по п. 5, в котором программируемое логическое устройство используется для ускорения одной или более функций блока распознавания вариантов.

8. Способ по п. 1, в котором данные описания графа дополнительно включают в себя (iii) данные, представляющие последний аппаратный логический блок из множества аппаратных логических блоков, выполняющих аппаратную логику на K-мерном графе или нуклеотидные последовательности, связанные с идентификатором K-мерного графа.

9. Система аппаратно-ускоренного генерирования K-мерного графа, представляющего множество ридов секвенирования для анализа распознавания вариантов, включающая:

секвенатор нуклеиновых кислот;

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

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

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

в процессе генерирования K-мерного графа:

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

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

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

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

12. Система по п. 9, дополнительно включающая:

один или более компьютеров; и

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

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

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

получение сгенерированного K-мерного графа с помощью блока распознавания вариантов; и

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

14. Система по п. 9, в которой данные описания графа дополнительно включают в себя (iii) данные, представляющие последний аппаратный логический блок из множества аппаратных логических блоков, выполняющих аппаратную логику на K-мерном графе или нуклеотидные последовательности, связанные с идентификатором K-мерного графа.

15. Способ аппаратно-ускоренного генерирования K-мерного графа, представляющего множество ридов секвенирования для анализа распознавания вариантов, в программируемом логическом устройстве, включающий:

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

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

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

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

конфигурирование устройством управления второго аппаратного логического блока для выполнения генерирования краев графа для сгенерированных узлов графа; и для одной или более пар сгенерированных узлов графа:

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

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

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

17. Способ по п. 15,

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

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

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

18. Способ по п. 15, в котором вторая аппаратная логика дополнительно выполнена с возможностью:

присвоить краевую массу каждому краю K-мерного графа.

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

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

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

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

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

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

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

21. Способ по п. 15, в котором устройство управления реализовано с использованием третьего аппаратного логического блока программируемого логического устройства.

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

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

24. Способ по п. 15, в котором данные описания графа дополнительно включают в себя (iii) данные, представляющие последний аппаратный логический блок из множества аппаратных логических блоков, выполняющих аппаратную логику на K-мерном графе или нуклеотидные последовательности, связанные с идентификатором K-мерного графа.

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

оценку K-мерного графа для проверки наличия циклов графа;

если во время оценки был обнаружен цикл графа:

прекращение построения K-мерного графа; или

если во время оценки цикл графа не обнаружен:

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

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

26. Система аппаратно-ускоренного генерирования K-мерного графа, представляющего множество ридов секвенирования для анализа распознавания вариантов, с использованием программируемого логического устройства, включающая:

секвенатор нуклеиновых кислот;

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

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

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

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

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

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

для одной или более пар сгенерированных узлов графа:

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

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

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

28. Система по п. 26,

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

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

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

29. Система по п. 26, в которой вторая аппаратная логика дополнительно выполнена с возможностью:

присвоения краевой массы каждому краю K-мерного графа.

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

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

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

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

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

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

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

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

33. Система по п. 26, в которой данные описания графа дополнительно включают в себя (iii) данные, представляющие последний аппаратный логический блок из множества аппаратных логических блоков, выполняющих аппаратную логику на K-мерном графе или нуклеотидные последовательности, связанные с идентификатором K-мерного графа.

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

оценку K-мерного графа для проверки наличия циклов графа;

если во время оценки был обнаружен цикл графа:

прекращение построения K-мерного графа; или

если во время оценки цикл графа не обнаружен:

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

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