RazerS - швидке зчитування з контролем чутливості
Девід Віз
1 кафедра комп'ютерних наук, Вільний університет Берліна, 14195 Берлін, Німеччина;
Енн-Катрін Емде
1 кафедра комп'ютерних наук, Вільний університет Берліна, 14195 Берлін, Німеччина;
Тобіас Рауш
2 Міжнародна дослідницька школа Макса Планка з обчислювальної біології та наукових обчислень, 14195, Берлін, Німеччина
Андреас Дерінг
1 кафедра комп'ютерних наук, Вільний університет Берліна, 14195 Берлін, Німеччина;
Кнут Райнерт
1 кафедра комп'ютерних наук, Вільний університет Берліна, 14195 Берлін, Німеччина;
Анотація
Технології секвенування другого покоління забезпечують безпрецедентно високу пропускну здатність даних послідовності ДНК. Загальним для більшості біологічних застосувань є відображення зчитувань до майже ідентичного або дуже подібного референтного геному. Завдяки великому обсягу даних, ефективні алгоритми та реалізації мають вирішальне значення для цього завдання. Ми представляємо ефективний інструмент відображення зчитування під назвою RazerS. Це дозволяє користувачеві вирівнювати зчитування послідовності довільної довжини, використовуючи або відстань Хеммінга, або відстань редагування. Наш інструмент може працювати як без втрат, так і з визначеними користувачем коефіцієнтом втрат на більш високих швидкостях. Враховуючи рівень втрат, ми представляємо підхід, який гарантує не втратити більше прочитаних даних, ніж зазначено. Це дозволяє користувачеві адаптуватися до проблеми і забезпечує плавний компроміс між чутливістю та часом роботи.
Технології секвенування другого покоління зробили революцію в області аналізу послідовності ДНК, оскільки можна отримати великі обсяги даних секвенування зі збільшенням швидкості та різким зменшенням витрат. Біологічне застосування різноманітне, включаючи повторне послідовне визначення цілого генома для виявлення геномних варіацій, наприклад, однонуклеотидні поліморфізми (SNP) (Bentley et al. 2008; Hillier et al. 2008; Ley et al. 2008; Wang et al. 2008) або великі структурні варіації (Chen et al. 2008), секвенування РНК для невеликого некодуючого виявлення РНК або профілювання експресії (Morin et al. 2008), програми метагеноміки (Huson et al. 2007) та секвенування хроматин-імунопреципітованої ДНК, наприклад, для ідентифікації місць зв'язування ДНК та моделей модифікації гістонів (Barski et al. 2007).
Фундаментальною для всіх цих додатків є проблема зіставлення всіх послідовних зчитувань проти еталонного геному, що позначається як проблема зчитування зчитування. Це можна формалізувати наступним чином: враховуючи набір послідовностей зчитування, посилальну послідовність G та відстань, знайдіть усі підрядки g G, які знаходяться на відстані k до зчитування. Входження g в G називаються збігами. Загальними мірами відстані є відстань Хеммінга або редагування відстані; перший забороняє вставляти та видаляти (тобто indels) у вирівнюванні, другий допускає невідповідність і indels.
Оскільки нові технології послідовності здатні виробляти мільйони зчитувань за пробіг, необхідні ефективні алгоритми для відображення зчитування. Зчитування, як правило, досить короткі порівняно з традиційними зчитуваннями Сангера і мають специфічний розподіл помилок залежно від використовуваної технології.
Різні інструменти були розроблені та розроблені спеціально для картографування коротких читань. Компіляція деяких популярних інструментів наведена в таблиці 1 разом із деякими ключовими характеристиками алгоритмів.
Таблиця 1.
Короткі прочитані засоби картографування з їх характеристиками
Більшість існуючих підходів до відображення читання використовують двоступеневу стратегію. По-перше, застосовується алгоритм фільтрації для ідентифікації регіонів-кандидатів, які, можливо, містять збіг. Це включає побудову структури даних індексу або на наборі зчитувань, або на послідовності посилань. По-друге, регіони-кандидати перевіряються на справжні збіги на більш трудомісткому етапі перевірки. У поточних реалізаціях слід ретельно розрізнити, чи обидва етапи, етап фільтрації та етап перевірки, адекватні вибраній відстані (Хеммінг або редагування відстані). Деякі реалізації, наприклад, перевіряють збіги, використовуючи якості базового виклику, але фільтрують регіони-кандидати, використовуючи фіксовану характеристику Хеммінга, або редагують відстань (H Li et al. 2008). Використовувані методи фільтрації засновані на одиночних (Kent 2002; Ma et al. 2002) або кількох насінні (Li et al. 2003; Lin et al. 2008), принципі голуб'ячої нори (Navarro and Raffinot 2002; H Li et al. 2008; R Li et al. 2008; AJ Cox, ELAND: Ефективне місцеве вирівнювання даних про нуклеотиди, не опубліковано), або на основі підрахунку лем з використанням (пробілу) q-грама (Burkhardt et al. 1999; Rasmussen et al. 2006; Rumble та Брудно 2008). Методи перевірки охоплюють напівглобальні алгоритми вирівнювання для Хеммінга або редагування відстані (Левенштейн 1966) або алгоритми локального вирівнювання (Сміт і Вотерман 1981).
BLAT (Kent 2002), як приклад одного насіннєвого фільтра, здійснює пошук точних випадків коротких фігурних підрядків, спільних для двох послідовностей. PatternHunter (Ma et al. 2002) був першим, хто узагальнив цю стратегію для насінин, що мають прогалини (загальні суміжні послідовності), тим самим підвищуючи чутливість, зберігаючи специфічність. Подальша чутливість досягається використанням кількох насінин із зазорами; підхід, реалізований в інструменті відображення зчитування Zoom (Lin et al. 2008), який використовує обмежену версію відстані редагування з щонайбільше одним пробілом. Після первинного подання цієї статті був опублікований метод, що використовує цілі зчитування як насіння, який допускає незначну кількість невідповідностей шляхом відстеження всіх можливих замін низькоякісних основ (Langmead et al. 2009). Він використовує трансформовані геноми Берроуза-Вілера та є ефективним підходом до короткого зчитування.