Случайности. Для кого-то все, что происходит вокруг, это одна сплошная случайность. А кто-то утверждает, что случайностей не бывает. Философствовать и спорить на эту тему можно много часов, а выводов все равно будет множество. Перейдя от метафизических размышлений к более реальным, можно увидеть, что случайные числа нашли свое применение во многих аспектах нашей жизни: от игровых автоматов до систем кодирования информации. Процесс, во время которого создается последовательность случайных чисел/символов, которую нельзя предугадать, именуется генерацией случайных чисел (ГСЧ). За долгую историю человечества было создано немало методов ГСЧ. Одни достаточно просты и понятны: игральные кости, монеты (орел/решка), колода карт и т.д. Другие же применяют куда более сложные физические процессы: к примеру, за счет высокочастотных движений электронов электрическое сопротивление провода не является постоянным, т.е. варьируется случайным образом. Измерив этот фоновый шум, можно получить последовательность случайных чисел. Но методики ГСЧ не ограничиваются исключительно физикой. Группа ученых из Швейцарской высшей технической школы Цюриха (или сокращенно ETHZ) создали новый метод генерации случайных чисел, основанный на синтезе ДНК. Как именно это было достигнуто, насколько случайны полученные число, и можно ли их предугадать? Ответы на эти вопросы ждут нас в докладе ученых. Поехали.
Основа исследования
В чем заключается одно из основных ограничений игральных костей как инструмента генерации случайных чисел? В том, что чисел этих будет не так и много (36 комбинаций костей, если утрировано, т.е. без вероятностей и прочего). Чем меньше вариаций мы имеем, тем проще предугадать возможный исход. Следовательно, для более сложного и, как следствие, безопасного кодирования на основе ГСЧ необходимо, чтобы генерируемых чисел было больше, а сами они были сложнее. Это очень упрощенное пояснение, тем не менее оно передает суть вопроса.
Варианты комбинаций двух игральны костей.
Посему использование тех физических процессов, которые невозможно точно предсказать, и стало основой многих современных методов ГСЧ. Однако стоит помнить, что существует два основных направления ГСЧ — генерация случайных (истинно случайных) и псевдослучайных чисел. В первом случае используется недетерминированный (хаотический) источник для генерации случайных чисел. Во втором создается детерминированная последовательность чисел, которая зависит от ввода (начального числа). Если входное начальное число известно, можно воспроизвести всю последовательность случайных чисел. НА первый взгляд, псевдо-ГСЧ кажется менее эффективной, однако этот метод обладает лучшими статистическими свойствами и часто может генерировать случайные числа гораздо быстрее, чем ГСЧ.
Вполне очевидно, что для генерации истинно случайных чисел подходят не только физические процессы или программные алгоритмы, но и химические реакции. С одной стороны, химические реакции являются статистическими процессами, при которых образование химических продуктов следует определенному распределению вероятностей в зависимости от энергии активации реакции. Но с другой стороны, возможность идентифицировать отдельные молекулы после синтеза практически нулевая, несмотря на возможность статистически предугадать исход реакции.
Ранее уже проводились исследования в области применения химии для генерации случайных чисел. К примеру, в данном труде описывается устройство, предоставляющее внушительный по размерам пул энтропии обнаруживаемых макросостояний растущих кристаллов в ходе химических реакций. Проблема в том, что невозможность идентифицировать отдельные молекулы приводит к потере случайности при анализе стохастических химических процессов. Другими словами, складывается впечатление, что химические реакции не подходят для ГСЧ. Однако, как заявляют сами авторы рассматриваемого нами сегодня труда, с синтезом ДНК ситуация совершенно иная.
Синтетическое производство ДНК это стохастический химический процесс обладающий важным преимуществом: отдельные молекулы в синтезированной последовательности ДНК могут быть легко идентифицированы и проанализированы с помощью современных технологий секвенирования (NGS от next generation sequencing). Само секвенирование существует еще с 1970-ых, однако нынешние методики позволяют считывать отдельные молекулы и, таким образом, использовать ДНК в качестве источника генерации случайных чисел.
Результаты исследования
Стоит отметить, что в биологии методы идентификации глобальных схем микробного компонента требуют синтеза случайных нуклеотидов в определенных положениях праймеров, чтобы оценить гипервариабельные области (например, для гена 16S рРНК) для таксономической классификации. Другие применения случайного синтеза нуклеотидов можно найти в штрих-кодировании, где с помощью уникальных молекулярных идентификаторов (UMI от unique molecular identifiers) можно устранить смещение амплификации ПЦР*.
Полимеразная цепная реакция (ПЦР)* — метод, позволяющий добиться значительного увеличения малых концентраций определенных фрагментов нуклеиновой кислоты (ДНК) в биологическом материале.
Ученые отмечают, что таковые случайные нуклеотиды отмечаются буквой N (по стандартам NC-IUB, т.е. номенклатурный комитет международного сообщества по биохимии). Следовательно, ученые использовали возможность синтезировать случайный нуклеотид для каждой позиции, обозначенной буквой N в конструкции используемого ДНК.
Изображение №1
Используемые в исследовании цепочки ДНК были сконструированы таким образом, что случайная область из 64 нуклеотидов вытекает из заданной области прямого праймера* на одном конце и заданной области обратного праймера на другом конце (изображение №1).
Праймер* — короткий фрагмент нуклеиновой кислоты.
Общая длина спроектированной цепи ДНК составила 105 нуклеотидов, включая две области праймера и случайную область.
Изображение №2
Спроектированная цепочка ДНК в последствии была физически реализована с использованием современных технологий твердотельного синтеза (изображение №2).
Смешивание строительных блоков ДНК-нуклеотидов также нашло применение в области ДНК хранения данных. Ранее проведенные исследования показали, что расширение алфавита* ДНК путем предварительного определения соотношения смешивания всех четырех нуклеотидов ДНК в определенных положениях в последовательности ДНК может повысить логическую плотность хранения данных за счет использования составных букв для синтеза ДНК.
Алфавит ДНК* — метод кодирования информации в молекулах ДНК посредством четырех букв: A (азотистые основания пуринового и пиримидинового типа аденин), T (тимин), G (гуанин) и C (цитозин).
Случайные последовательности ДНК были синтезированы три раза: дважды компанией Microsynth и один раз Eurofins Genomics. Для первой компании была поставлена дополнительная задача смешать строительные блоки перед объединением (синтез 1). Вторая же компания производила синтез без каких-либо дополнительных вмешательств в процесс (синтез 2).
В результате синтез 1 дал 204 мкг высушенной ДНК, синтезированной от 3′ к 5′ направлению. Чтобы определить случайность, пул ДНК был секвенирован и впоследствии подвергнут цифровой фильтрации.
Если посмотреть на состав цепей ДНК как функцию положения в случайной области (изображение №3), то можно заметить две общие тенденции:
- нуклеотидная неэквивалентность: во всех синтезах процент нуклеотидов G и Т выше, чем процент нуклеотидов A и C;
- неэквивалентность позиций: в то время как процентное содержание A и C является относительно постоянным в цепочке из 60 нуклеотидов, процентное содержание G уменьшается с 5′ до 3′, а процентное отношение T увеличивается с 5′ до 3′. Данная тенденция наблюдалась чаще в образцах от Microsynth (со смешиванием строительных блоков), чем от Eurofins (без смешивания).
Изображение №3
Наблюдаемые тенденции дают первое представление о надежности данных и частично могут быть объяснены химическими процессами, происходящими во время синтеза ДНК. Несоответствие процентного содержания нуклеотидов G, T и A, C (нуклеотидная неэквивалентность) может быть вызвано несколькими факторами. По заявлению компании Microsynth, объемы отдельных строительных блоков в ходе синтеза не контролируются с точностью до микролитра.
Следовательно, различия в концентрации могут приводить к менее однородному распределению нуклеотидов вдоль цепи. Кроме того, эффективность связывания различается для каждого строительного блока и зависит от таких переменных, как период использования реагентов для синтеза производителями или защитных групп, присоединенных к каждому строительному блоку. Результат разной эффективности связывания, скорее всего, связан с неравномерным распределением четырех нуклеотидов.
Уменьшение G и увеличение T от 5′ до 3′ (неэквивалентность позиций) может быть результатом химической процедуры, которую цепь ДНК испытывает во время синтеза. Поскольку синтез ДНК протекает в направлении 3′ – 5′, нуклеотиды в положении 60 (изображение №3), сначала добавляются к цепи ДНК. Так как синтезированные фрагменты ДНК остаются в камере для синтеза до тех пор, пока не будет получена желаемая длина цепи ДНК, нуклеотиды, добавленные к цепи ДНК в начале синтеза, дольше всего остаются в среде синтеза. Таким образом, эти нуклеотиды прошли большинство стадий синтеза и, следовательно, большинство стадий окисления.
Эта характеристика производительности химического синтеза ДНК может быть объяснением тенденции №2 (неэквивалентность позиций), когда состав G уменьшается вдоль цепи в 5′ – 3′ направлении, а состав T увеличивается в 5′ – 3′ направлении.
Окисление может привести к явлению, называемому трансверсией G – T (3e), при котором основание G химически изменяется таким образом, что на этапах репликации ДНК оно может быть заменено на основание T.
Кроме вышеописанных тенденций отличия в кривых на графиках может быть связано с различиями в стратегии синтеза (со смешиванием строительных блоков и без смешивания).
Существует два основных потенциальных источника погрешности, которые могут повлиять на результаты: погрешность из-за покрытия (когда часть исследуемых элементов находится за пределами исследуемой области) и погрешность из-за ошибок.
Первый вариант преимущественно выражается погрешностью, которая может быть связана с пространственным расположением на чипе синтеза и стохастичностью ПЦР. Второй вариант является результатом вставок, делеций (хромосомных перестроек, когда теряется участок хромосомы) или замен ошибочных нуклеотидов на этапах синтеза, ПЦР и секвенирования.
В данном конкретном исследовании погрешность из-за покрытия влияет на распределение нуклеотидов только в том случае, если существует значительное расхождение между покрытием каждой случайной последовательности. Однако анализ данных показал, что данный вариант погрешности не может быть причиной наблюдаемой неэквивалентности нуклеотидов и неэквивалентности положения.
Что касается погрешности из-за ошибок, то крайне сложно различить ошибки синтеза и секвенирования, так как эти два процесса не могут быть полностью разделены, поскольку доступ к молекулярной морфологии ДНК возможен только через секвенирование ДНК. Однако исследования показали, что при соответствующей обработке данных ошибки секвенирования возникают в случайных местах.
Во время синтеза ДНК рост цепочек может быть прерван до достижения желаемой длины и, таким образом, вызвать погрешность в пуле. А вот процесс секвенирования не показал существенного влияния на результат (3a—3c). Следовательно, погрешности из-за ошибок вызваны исключительно процессом синтеза ДНК, а не секвенирования.
Путем нормализации синтеза 1 (3a) была получена тепловая карта, иллюстрирующая преобладание связывания двух нуклеотидов (3d). Также она позволяет увидеть третью погрешность: преобладание связывания нуклеотидов.
Связывания одного основания с существующим нуклеотидом частично зависит от природы существующего нуклеотида: G реже связывается с A, если он имеет возможность свободно связываться с A, T, C или G; при этом G чаще связывается с G, если он может свободно связываться с A, T, C или G.
С точки зрения синтеза, исправить данную неточность можно достаточно просто. К примеру, можно добавить больше T блоков вместо G (таким образом, поменяв заданное соотношение нуклеотидов A, G, T и C), что приведет к увеличению смещения от трансверсии.
Однако, ввиду сложности этого процесса, ученые решили в рамках исследования не проводить «физические» правки, а использовать вычислительный алгоритм постобработки, чтобы удалить смещение, созданное во время синтеза ДНК, увеличивая надежность и воспроизводимость всей процедуры.
На этапе обработки данный (т.е. на этапе подготовке к ГСЧ) был использован пул, полученный из синтеза 1 (Microsynth). Хотя этот вариант показывает самое сильное смещение, возникающее в результате трансверсии, плавные кривые показывают наиболее однородные смешивание и соединение на этапах синтеза.
Считывание случайности из синтезированных цепей ДНК требует считывания отдельных цепей, что было осуществлено с помощью секвенирования (в данном случае использовалась система iSeq100). После секвенирования выходные данные (цифровой файл) обрабатывались так, чтобы отобрать верные (т.е. без ошибок) последовательности из пула.
Ошибки, которые могли возникнуть, включают ошибки делеции, вставки и замены. Они могут привести к тому, что цепочка ДНК будет слишком короткой, слишком длинной или будет содержать поврежденное основание. Чтобы свести к минимуму влияние ошибок (особенно ошибок из-за делеции) на случайность, все последовательности были сокращены до 60 нуклеотидов. Из полученных цепей выбирались исключительно те, что содержали правильную длину случайных нуклеотидов.
После того как пул обработанной компьютером ДНК был ограничен (только последовательности 60 нуклеотидов в длину), нуклеотиды ДНК были сопоставлены с битами с использованием следующей схемы: A → 0, C → 0, T → 1, G → 1. Вследствие этого оцифрованная цепочка ДНК была преобразована в двоичный код.
Строки битов (битовые потоки), полученные после сопоставления, были впоследствии проверены на случайность с использованием набора статистических тестов NIST. Ученые уверяют, что их метод оценки случайностей был крайне жестким: последовательность считалась достаточно случайной лишь тогда, когда успешно проходила все тесты по отдельности (если хотя бы один тест был провальный, последовательность исключалась).
Оценка первоначальных битовых потоков с использованием набора статистических тестов NIST показала, что не все тесты прошли успешно. Это означает, что полученные битовые потоки не обладают такими же статистическими свойствами, как полностью случайная последовательность, т.е. они все еще содержат некоторую избыточность и смещение. Потому была необходима дополнительная битовая обработка для удаления смещения, возникшего еще на этапе синтеза ДНК.
Дабы решить проблему смещения выходных битов (когда одних чисел больше, чем других), ученые решили использовать алгоритм фон Неймана. Алгоритм рассматривает биты в последовательности попарно, а потом выполняет одно из трех действий: если два последовательных бита равны, они удаляются (не учитываются); последовательность «1, 0» преобразуется в единицу; последовательность «0, 1» преобразуется в ноль.
В контексте данного исследования ожидалось, что алгоритм фон Неймана будет работать следующим образом:
- если на входе «0, 1» или «1, 0», первая цифра становится выходом, а вторая цифра отбрасывается;
- если на входе «0, 0» или «1, 1», выход отсутствует, потому обе входные цифры отбрасываются.
Одним из крупнейших недостатков данного метода является большая потеря данных: около 75% входных данных отбрасывается ввиду его работы. Следовательно, вводные данные должны быть достаточно большими, чтобы компенсировать дальнейшие потери.
Изображение №4
Эффект нивелирования смещения (схема выше) хорошо виден при анализе разницы между необработанными битовыми потоками (содержащими смещение) и обработанными битовыми потоками (без смещения).
Кумулятивная сумма каждого необработанного битового потока (каждый длиной 60 нуклеотидов) и каждого обработанного битового потока (каждый длиной менее 60 нуклеотидов) была рассчитана путем присвоения каждому 0 значения «-1» и каждой 1 значения «1». Далее, все потоки битов без смещения были объединены в один битовый блок.
Ученые отмечают, что хоть потеря данных и значительна (потеряно более 75% всех битов), а вычислительная эффективность довольно низка (средняя скорость вывода данных в четыре раза медленнее, чем средняя скорость ввода данных), устранение смещения было выполнено идеально (на выходе смещение полностью отсутствует).
Битовый блок, полученный после обработки алгоритмом фон Неймана, повторно прошел оценку через систему NIST.
Таблица №1: результаты статистических тестов NIST.
Все обработанные битовые потоки успешно прошли статистические тесты NIST с проходным баллом для каждого теста > 54/56, что превышает статистически необходимый минимум (52/56). Дальнейшая оценка битового потока показала, что P-значение ≥ 0.001. Из этого следует, что последовательность случайна с достоверностью в 99.9%.
Изображение №5
Схема выше представляет собой полный процесс генерации случайных чисел с помощью синтеза ДНК. Как мы помним, в результате синтеза было получено 204 мкг ДНК, что соответствует примерно 4х1015 нитям ДНК. Процесс синтеза такого количества ДНК занимает порядка 8.75 часов, а стоимость производства составляет около 100 долларов США.
Образец сухой ДНК содержит теоретическую энтропию в 28 ПБ (если нет смещения в данных) и 7 ПБ случайностей при удалении смещения с использованием алгоритма фон Неймана (т.е. после потери 75% битов). Следовательно, в отличие от хранения данных с помощью ДНК, сам синтез не является узким местом (фактор ограничения производительности) в генерации случайных чисел, поскольку он может генерировать случайность со скоростью 225 гигабайт в секунду при затратах 0.000014 $/ГБ.
Однако секвенирование, наоборот, является узким местом в аспекте временных и финансовых затрат на обработку. Использованная в данном труде система iSeq имеет более производительные варианты (например, NovaSeq 6000), способные выполнять до 20 миллиардов считываний последовательностей за 36 часов. Финансовые затраты при этом довольно внушительны ($ 22000). Следовательно, учитывая все этапы ГСЧ, результат можно получать со скоростью 300 килобайт в секунду по цене 600 долларов за ГБ. Снизить затраты возможно за счет объединения нескольких походов синтеза и секвенирования.
Для более подробного ознакомления с нюансами исследования рекомендую заглянуть в доклад ученых и дополнительные материалы к нему.
Эпилог
Генераторы случайных чисел существуют уже тысячи лет (древнейшим игральным костям, найденным в Иране, порядка 5200 лет), пусть даже люди тех времен и не знали их полного потенциала. Современные технологии и научный прогресс позволили им создавать сложные алгоритмы и устройства, способные генерировать случайности, которые человеку будет невозможно предугадать. Однако, где человек отстает, технологии нагоняют. Другими словами, где есть шифр, есть и дешифровщик. Посему постепенное совершенствование методов кодирования информации, где применяются генераторы случайных чисел, вызывает параллельное совершенствование методов взлома таких систем. Эта бесконечная гонка замков и отмычек требует от обеих сторон постоянно придумывать все новые и новые методы.
Многие современные ГСЧ основаны на физических процессах и алгоритмах. Но вот химические реакции долгие годы были в стороне, так как считалось, что они не могут быть надежным фундаментом для ГСЧ. В данном труде ученые показали, что синтез ДНК, будучи химическим процессом, может быть не только достойным вариантом основы для ГСЧ, но и во многих аспектах превосходить своих «физических» конкурентов.
Естественно, данный метод пока еще является неограниченным алмазом, требующим шлифовки в виде дополнительных исследований, целью которых будет повышение производительности и снижение стоимости. Тем не менее генерация случайных чисел посредством ДНК является крайне перспективным направлением уже сейчас.
Благодарю за внимание, оставайтесь любопытствующими и хорошей всем рабочей недели, ребята. 🙂
Немного рекламы
Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).
Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
