Дата зміни інформації:

Костогриз В. П. “ТЕХНОЛОГІЯ NVIDIA CUDA ДЛЯ ВИРІШЕННЯ ЗАДАЧ НА ОСНОВІ SMITH-WATERMAN АЛГОРИТМУ В БІОІНФОРМАТИЦІ”

Костогриз В. П., викладач-стажист кафедри інформатики і ІКТ

Уманський державний педагогічний університет

імені Павла Тичини

 

Біоінформатика є застосування комп’ютерних наук і технологій для управління та аналізу біологічних даних, з метою вирішення біологічних питань.

Пошук баз даних ДНК і білкових послідовностей є однією з основних задач в області біоінформатики. Smith-Waterman (SW) алгоритм гарантує максимальну чутливість для локального вирівнювання послідовностей, але це повільно. Багато було спроб прискорити алгоритм SW за допомогою або програмного забезпечення або апаратних засобів.

Технологія NVIDIA ® CUDA ™ – архітектура паралельних обчислень, що дозволяє різке збільшення обчислювальної продуктивності шляхом використання потужностей GPU (графічного процесора). У цій статті ми розглядаємо деякий досвід у застосуванні CUDA для широкого комплексу проблем біоінформатики на GPU.

Вирівнювання послідовностей має довгу історію в геноміці, і як і раніше є ключовим компонентом аналізу генів і геномів. Простіше кажучи, алгоритми вирівнювання послідовності знаходять ділянки в одній послідовності, що називається послідовністю запиту, які аналогічні або ідентичні ділянкам в іншій послідовності, так званої опорної послідовності. Такі ділянки можуть представляти гени, що зберігають регуляторні ділянки, або будь-яку з безлічі інших функцій послідовності. Вирівнювання також відіграє центральну роль в de novo і порівняльнному аналізі геному, де тисячі або мільйони послідовностей зчитування приведені у певну відповідність один до одної або з раніше приведеними послідовностями геному з посилання. Щодо нових, недорогих великомасштабних технологій секвенування, тепер можна генерувати величезну кількість даних про послідовності в дуже короткий проміжок часу, що дозволяє дослідникам, що намагаються секвенування геном, виконнання проектів в набагато більшому масштабі, ніж раніше. Вирівнювання цих послідовностей з використанням сучасних алгоритмів вимагає дуже високої продуктивності комп’ютера в даний час доступних тільки в найбільших біоінформатичних центрах.

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

Подібність послідовності можна визначити, обчисливши її за допомогою локального вирівнювання та динамічного програмування на базі Smith-Waterman (SW) алгоритму. Однак вартість такого підходу є дорогим з точки зору часу обчислень і пам’яті. Це особливо очевидно в зв’язку з швидким зростанням біологічних баз даних послідовностей, що вимагає потужних високопродуктивних обчислювальних рішень. Завдяки обчислювальним потужностям, характеру алгоритму SW, деякі евристичні рішення, такі як FASTA і BLAST, були розроблені, щоб покращити швидкість виконання, але за рахунок чутливості. Це може привести до того, що деяких віддалено-споріднених послідовностей не буде виявлено.

Сучасні реалізації алгоритму SW в основному зосереджена на GPU- технологіях обчислень [1,2].

Smith-Waterman (SW) алгоритм є відомим алгоритмом в області біоінформатики, який знаходить оптимальне узгодження між двома ДНК або білоковими послідовностями. Визначення того, наскільки добре вирівняні дві послідовності грає важливу роль у виявленні гомологічних генів і вивченні історії еволюції молекул. Проте, алгоритм SW зазвичай не використовується для пошуку баз даних послідовністей, тому що це занадто повільно, при використанні його для багатьох послідовностей. Замість цього використовуються швидші евристичні алгоритми, такиі як FASTA і BLAST, хоча вони не можуть гарантувати, що якісна оцінка для оптимального вирівнювання буде здійснена локальним. Таким чином, для досягнення збільшення швидкості і оптимального вирівнювання, необхідно розробити підхід до скорочення часу обробки алгоритму SW. Алгоритм SW спочатку створюється як двовимірний (2D) на основі матриці з розміром, рівним довжині двох послідовностей ДНК. Оцінка кожної клітинки матриці розраховується виходячи з сусідніх клітинок. Оптимальна оцінка відповідності між двома послідовностями ДНК на  найбільшу кількість очок в матриці і відповідне вирівнювання визначається трасуванням із задньої клітинки з найбільшою кількістю очок до першої клітинки з нульовим рахунком.

Багато спроб було прискорити алгоритм SW за допомогою або програмного або апаратного забезпечення, зосередивши увагу на паралельній обробці матриці. Відповідне прискорення було реалізована за допомогою VLSI (Very Large Scale Integration) і FPGA (Field Programmable Gate Array), одночасно оцінюючи клітинки уздовж малої діагоналі матриці. Альтернативна реалізація була використана останнім часом для прискорення алгоритмів SW за допомогою програмного забезпечення паралельного програмування на загальних мікропроцесорах зі швидкістю поліпшення до шести разів. Алгоритм SW відноситься до класу алгоритмів, відомих як динамічне програмування. Динамічне програмування застосовується при великому просторовому пошуку та може бути структуроване в послідовності етапів, що на початковому етапі містить тривіальні рішення підзадач.

GPU CUDA реалізація SW алгоритму є доступною та є швидшою, ніж попередні версії, а також знімає обмеження на запит довжини послідовності. Хоча програмне забезпечення виконує оптимальне Smith-Waterman вирівнювання ще швидше, ніж програмні евристичні програмні рішення, такі як FASTA і BLAST [3].

Результати тестової роботи показують, що нові CUDA сумісні графічні карти в даний час розвинулися достатньо, щоб вважатися ефективними апаратними прискорювачами для Smith-Waterman алгоритму. Висока швидкість може бути отримана з найбільшою чутливістю алгоритму.

Було виявленно певну взаємозалежність у спаданні швидкості досліджуваного SW-алгоритму в залежності від CPU/GPU конфігурації. Відносно досліджуваного алгоритму було застосовано CPU/GPU конфігурацію виду nCPU+mGPU, де n= 0, m=1;2 та n=1, m=1;2.

Ефект зниження швидкості виконнання SW алгоритму спостерігається на основі розподілу його потоків між CPU та GPU одночасно та рівномірно, у конфігурації  nCPU+mGPU, де n=1, m=1;2, а ефект збільшення продуктивності -при nCPU+mGPU, де  де n= 0, m=1;2, де продуктивність алгоритму зростає лінійно при відповідному значенні E(n), де E(n) – коефіцієнт лінійності , звідси випливає залежність максимальної продуктивності від специфікації та конфігурації nCPU та mGPU та відповідного збалансування їх продуктивності відносно паралельного алгоритму.

Результати роботи показують, що нові CUDA сумісні графічні карти в даний час еволюціонували достатньо, щоб вважатися ефективними апаратними прискорювачами для Smith-Waterman алгоритму. Висока швидкість може бути отримана з найбільшою чутливістю алгоритму.

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ:

  1. Svetlin A. Manavski, Giorgio Valle, CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment, BMC Bioinformatics 2008, 9(Suppl 2):S10.
  2. NVIDIA CUDA C Programming Guide [Електронний ресурс]. – Режим доступу: https://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf.
  3. Liu, D.L. Maskell, B. Schmidt. CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units, BMC Research Notes 2009, p.10.

 

 

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

Введіть цифри, що зображені у квадратах *