Phylo — экспериментальная видеоигра обоптимизации множественного выравнивания последовательностей . [1] Разработанная Центромбиоинформатики Макгилла , она изначально была выпущена как бесплатная Flash- игра в ноябре 2010 года. Разработанная как игра с целью , игроки решают головоломки сопоставления шаблонов, которые представляют собой последовательности нуклеотидов различных филогенетических таксонов , чтобы оптимизировать выравнивания по компьютерному алгоритму. Выравнивая вместе каждую последовательность нуклеотидов, представленную в виде разноцветных блоков, игроки пытаются создать наивысшую оценку очков для каждого набора последовательностей, сопоставляя как можно больше цветов и минимизируя пробелы.
Нуклеотидные последовательности, сгенерированные Phylo , получены из фактических данных последовательностей из UCSC Genome Browser . Высоко оцененные выравнивания игроков собираются как данные и отправляются обратно в Центр биоинформатики Макгилла для дальнейшей оценки с помощью более сильного алгоритма подсчета очков. Те выравнивания игроков, которые набрали больше очков, чем текущая оценка, сгенерированная компьютером, будут повторно введены в глобальное выравнивание в качестве оптимизации.
Целью множественных выравниваний последовательностей в филогенетике является определение наиболее вероятной нуклеотидной последовательности каждого вида путем сравнения последовательностей дочерних видов с последовательностями самого недавнего общего предка . Создание такого оптимального множественного выравнивания последовательностей обычно определяется с помощью алгоритма динамического программирования, который находит наиболее вероятный эволюционный результат путем минимизации количества требуемых мутаций . Эти алгоритмы генерируют филогенетические деревья для каждого нуклеотида в последовательности для каждого вида и определяют генетическую последовательность для общего предка путем сравнения деревьев дочерних видов. Затем алгоритмы оценивают и сортируют завершенное филогенетическое дерево, и выравнивание с максимальной оценкой экономичности определяется как оптимальное и, следовательно, наиболее эволюционно вероятное множественное выравнивание последовательностей. Однако нахождение такого оптимального выравнивания для большого количества последовательностей было определено как NP-полная задача.
Phylo использует человеческие вычисления для создания интерактивного генетического алгоритма для решения проблемы множественного выравнивания последовательностей. Генерация предковых последовательностей и оценка экономичности по-прежнему вычисляются с использованием вариации метода Фитча-Марголиаша , но Phylo абстрагирует генетические последовательности, полученные из браузера генома UCSC, в игру сопоставления шаблонов, позволяя игрокам-людям предлагать наиболее вероятное выравнивание, а не алгоритмически рассматривать все возможные деревья.
Каждая головоломка в Phylo категоризируется на основе общего количества фрагментов последовательности, которые необходимо выровнять, и заболевания, которое связано с этим фрагментом у людей. После выбора головоломки несколько фрагментов генетической последовательности для каждого вида, которые необходимо выровнять, представленные в виде цветных блоков, размещаются в одной строке сетки. Каждый нуклеотид фрагмента генетической последовательности может свободно перемещаться по сетке. Затем игроки могут корректировать последовательности по мере необходимости, чтобы создать наибольшее количество цветовых совпадений в каждом столбце между ними, при этом минимизируя количество появляющихся пробелов.
Подсчет очков за выравнивание последовательностей производится путем сравнения каждой из выровненных игроком последовательностей с определенной алгоритмом предковой последовательностью, сгенерированной в каждом узле. Совпадение цвета дает +1 к счету, несовпадение дает -1, открытие пробела дает -5, а расширение любого существующего пробела дает -1. Затем каждые несколько секунд определяется сумма всех сравнений, которая дает окончательный счет за выравнивание этого игрока. Для каждой головоломки в начале игры изначально доступно только несколько последовательностей. Игрок должен побить определенный компьютером номинальный счет, прежде чем перейти к следующему раунду и разблокировать больше последовательностей для сопоставления. Игрок выигрывает и ему разрешается отправить свое выравнивание последовательностей в базу данных, совпав или превзойдя окончательный номинальный счет, сгенерированный компьютером для каждой головоломки.
По состоянию на май 2019 года [обновлять](версия 3.1.5) в Phylo доступны три игровых режима:
По сравнению с компьютерным выводом, игроки смогли улучшить 70% выравниваний. [1] В 2013 году разработчики Phylo создали веб-сервер под названием Open-Phylo (ныне несуществующий), который позволяет исследователям загружать собственные наборы последовательностей для игроков для выравнивания. По сравнению с компьютерными выравниваниями, опытные игроки смогли в основном внести небольшие улучшения по сравнению с тем, что могли сделать алгоритмы выравнивания последовательностей. Было также несколько незначительных случаев значительно лучших выравниваний, предложенных людьми. [3] Отчет 2017 года по пятилетним историческим данным Phylo приходит к аналогичному выводу. [4]