Википедия

BWA (выравнивание биологических последовательностей)

BWA (англ. Burrows-Wheeler Aligner) — программный пакет для картирования коротких прочтений на большие референсные геномы (такие как, например, геном человека[2]), написанный китайским биоинформатиком Хенг Ли[en] и англичанином Ричардом Дурбиным[en]. Является одним из широкоиспользуемых алгоритмов выравнивания[3][4][5], а также рекомендуется для анализа данных производителями Illumina[6]. BWA состоит из трёх основных алгоритмов: BWA-BackTrack, BWA-SW и BWA-MEM. В основе алгоритмов BWA лежит преобразование Барроуза—Уилера, суффиксные массивы и алгоритм выравнивания Смита—Ватермана. Программный пакет умеет работать с длинными последовательностями на порядок быстрее, чем MAQ (англ. Mapping and Assembly with Qualities) при достижении аналогичной точности выравнивания[7].

BWA
Тип Биоинформатика
Авторы Хенг Ли[en], Ричард Дурбин[en]
Написана на C++
Операционные системы UNIX, Linux
Последняя версия 0.7.17 (r1140)[1] (07.11.2017)
Лицензия GNU GPL, MIT License
Сайт bio-bwa.sourceforge.net

Для образцов c платформ Illumina-SOLEXA, 454 Life Sciences, ионного полупроводникового секвенирования или секвенирования по Сэнгеру с длиной чтений («ридов» от англ. read — «чтение, прочтение»; отдельные фрагменты ДНК, полученные в результате работы секвенатора) больше или равных 70 пар оснований (здесь и далее — п.о.), BWA-MEM обычно предпочтительней. BWA-MEM и BWA-SW имеют схожие функции, такие как, например, поддержка длинных прочтений. BWA-MEM имеет лучшую производительность, чем BWA-BackTrack для чтений длиной 70—100 п.о. с платформы Illumina-SOLEXA.

Независимо от выбранного алгоритма программный пакет BWA сначала должен построить FM-индекс для референсного генома. Для создания индекса используется следующая команда: bwa index [-p prefix] [-a algoType] <in.db.fasta>. Далее к полученным данным применяются алгоритмы выравнивания, которые вызываются различными подкомандами: aln/samse/sampe для BWA-BackTrack, bwasw для BWA-SW и mem для BWA-MEM[8].

История править

Хенг Ли, научный сотрудник Кембриджского института Броуда[9], начал писать первую часть кода 24 мая 2008 года и получил первоначальную стабильную версию уже 2 июня того же года. В этот же период профессор Tak-Wah Lam, первый автор статьи BWT-SW[10], сотрудничал с Пекинским геномным институтом[en] в работе над SOAP2, преемником SOAP (пакет анализа коротких олигонуклеотидных последовательностей). SOAP2 вышел в ноябре 2008 года.

Алгоритм BWA-SW является новым компонентом BWA. Он был задуман в ноябре 2008 года и реализован спустя десять месяцев. По состоянию на 2015 год BWA-MEM (0.7.10) считался более предпочтительным в использовании для поиска снипов, чем bowtie (2-2.2.25) или Novoalign (3.02.12)[11].

Использование править

Программный пакет BWA может быть использован в таких областях, как генотипирование для поиска однонуклеотидных полиморфизмов (снипов)[12]. Генотипирование позволяет проводить индивидуальное сравнение генотипов разных людей, с помощью него можно предсказывать предрасположенность людей к всевозможным заболеваниям, таким как, например, рак, диабет и многие другие. Так же пакет будет полезен в транскриптомике[13].

Начиная с версии 0.6.x, все алгоритмы могут работать с геномами, общая длина которых превышает 4 Гб[8]. Тем не менее, размер индивидуальной хромосомы не должен превышать 2 Гб. Каждый алгоритм вызывается отдельной командой, принимает входной файл через стандартный поток ввода («stdin») и возвращает результат через стандартный поток вывода («stdout»).

BWA-BackTrack править

Сначала строится суффиксный массив, а затем генерируется BWT. Неопределённые нуклеотиды (обозначаются литерой «N») в референсном геноме преобразуются в случайные нуклеотиды, а в чтениях рассматриваются как несовпадения. Это может привести к регионам ложных совпадений («хитов») с неоднозначными основаниями. Но вероятность того, что это может произойти очень небольшая, учитывая относительно длинные чтения[14].

BWA-SW править

BWA-SW строит FM-индексы и для референсной последовательности и для чтений. Он неявно представляет собой референсную последовательность в виде префиксного дерева и чтения в виде детерминированного ациклического конечного автомата, который составляется из префиксного дерева для чтения с использованием динамического программирования. В отличие от BLAT и SSAHA2, BWA-SW находит сиды (от англ. seed — «семя»; точное совпадение нескольких пар оснований чтения[4]) в референсном геноме с помощью построения FM-индексов. Выравнивание расширяется тогда, когда сид имеет несколько вхождений в эталонной последовательности. Скорость достигается за счёт уменьшения ненужного расширения для высоко повторяющихся последовательностей. По сравнению со стандартным выравниванием Смита — Ватермана, временная сложность которого равна  , BWA-SW имеет лучшую временную сложность так как он, как минимум, не медленнее, чем BWT-SW, сложность которого —   [10]. В BWA-SW два выравнивания считаются различными в том случае, если длина зоны перекрытия по запросу составляет менее половины длины более короткого сегмента запроса.

Реализация BWA-SW принимает индекс BWA и FASTA запроса или FASTQ файла в качестве входных данных и выводит выравнивание в формате SAM. Входной файл, как правило, содержит много последовательностей («ридов»). Каждая последовательность обрабатывается, в свою очередь, с использованием нескольких потоков (если это возможно). Использование памяти при работе с данным алгоритмом составляет около 5 Гб для индексирования полных последовательностей генома человека[8]. Для коротких прочтений требуется приблизительно 3,2 Гб при использовании команды aln и 5,4 Гб при использовании sampe. Необходимый объём памяти для каждого запроса примерно пропорционален длине последовательности. Кроме того, BWA-SW способен обнаружить химеру, потенциально вызванную структурными изменениями или эталонными ошибками сборки ридов, которые могут представлять угрозу для BLAT и SSAHA2. BWA-SW отличается от BWT-SW в нескольких аспектах[15]: BWT-SW гарантирует, что найдёт все локальные совпадения, в то время как BWA-SW представляет собой эвристический алгоритм, который может пропустить истинные совпадения, но работает гораздо быстрее.

BWA-MEM править

BWA-MEM является последним реализованным алгоритмом пакета BWA. Он использует стратегию, в которой алгоритм выравнивания прочтений выбирается автоматически в каждом конкретном случае: локальное или глобальное выравнивание. Поддерживаются парноконцевые прочтения и выравнивания химерных прочтений. Алгоритм устойчив к ошибкам секвенирования и применим к широкому диапазону последовательности длиной от 70 п.о. до нескольких мегабаз. А для картирования последовательностей длинной 100 п.о. BWA-MEM показывает лучшую производительность, чем некоторые передовые алгоритмы выравнивания прочтений[16].

Показатели качества править

Для каждого выравнивания программный пакет BWA вычисляет оценку качества картирования — Phred масштабированную вероятность того, что выравнивание является некорректным[8] (англ. Phred quality score​ — оценка качества прочитанного нуклеотида ДНК). Необходимость статистической оценки картирования возникает из-за того, что риды получаются маленькие (40—100 п.о), а геномы достаточно большие, поэтому выравниваний может быть несколько. Тем не менее, необходимо понять, какое из них наиболее информативное. И по сути Phred-оценка представляет собой вероятность того, что рид выравнен неправильно. Вычисляется она по формуле  , где q — качество прочтения рида[17]. Алгоритм аналогичен оценке для MAQ, за исключением того, что в BWA предполагается, что истинное совпадение всегда может быть найдено. Такое изменение было сделано в связи с тем, что формула MAQ переоценивает вероятность пропуска истинного совпадения, что приводит к заниженному качеству картирования. Моделирование показывает, что BWA может переоценивать качество картирования из-за этой модификации, но отклонение относительно невелико.

Примеры править

Пример сценария использования программного пакета BWA от Голландского вычислительного центра выглядит следующим образом[18]:

Шаг 1 — индексирование генома (∼3 CPU часа для генома человека)
bwa index -a bwtsw ref.fa

,где ref.fa — название файла с референсным геномом.

Шаг 2а — генерирование выравнивания в координатах суффиксного массива
bwa aln ref.fa read1.fq.gz > read1.sai
bwa aln ref.fa read2.fq.gz > read2.sai

,где read1.fq.gz — файл с прямыми чтениями, read2.fq.gz — обратными чтениями. Применяем параметр -q15, если качество меньше на 3’-концах чтений.

Шаг 3а — генерирование выравнивания в SAM формате для парноконцевых чтений
bwa sampe ref.fa read1.sai read2.fq.gz > aln.sam
Шаг 4a — генерирование выравнивания в SAM формате для непарноконцевых чтений
bwa samse ref.fa read1.sai read1.fq.gz
Шаг 2б — BWA-SW для длинных чтений
bwa bwasw ref.fa long-read.fq.gz > aln-long.sam

,где long-read.fq.gz — файл с длинными чтениями.

Для дальнейшей совместимости полученного выравнивания со стандартными программами для анализа NGS данных, таких как, например, Pikard Tools или GATK, при вызове программы следует указывать так называемую группу прочтения (англ. read group — набор данных, полученных с помощью одного режима работы секвенсора) добавлением флага -r[19]. Сама группа прочтения для образца с платформы Illumina-SOLEXA выглядит примерно следующим образом: -r ‘@RG\tID:1\tSM:S000336\tPL:ILLUMINA\tLB:L00000336\t PU:C3A7NACXX:1’[19], где ID — это уникальный идентификатор данного образца, SM — это названия образца, Pl — это платформа для секвенирования, LB — название библиотеки, а PU — системный идентификатор[20].

Практическое значение править

На практике BWA является основным инструментом, предназначенным для выравнивания коротких ридов[21][22][23][24]. В настоящее время BWA применяется в следующих исследованиях:

  • Секвенирование и сборка генома.
  • Поиск однонуклеотидных полиморфизмов.
  • Поиск делеций и вставок.

Основными преимуществами использования программного комплекса BWA являются следующие его достоинства[7][25]:

  • Высокая скорость работы[26]
  • Небольшие затраты по памяти.
  • Простой интерфейс.
  • При тонкой настройке лучшие статистические параметры[27]

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

Примечания править

  1. ↑ Heng Li. BWA Releases (англ.). GitHub. Дата обращения: 5 апреля 2017. Архивировано из оригинала 5 апреля 2017 года.
  2. ↑ Гольцов А.Ю., Андреева Т.В., Решетов Д.А., Тяжелова Т.В., Гаврик О.А., Рогаев Е.И. Поиск мутаций в генах митохондриальной ДНК, ассоциированных с развитием болезни Альцгеймера, с использованием технологии параллельного секвенирования // Современные проблемы науки и образования : журнал. — М.: Российская академия естествознания, 2012. — № 6. — С. 23. — ISSN 1817-6321. Архивировано 5 апреля 2017 года.
  3. ↑ Ivan Borozan, Stuart N. Watt, Vincent Ferretti. Evaluation of Alignment Algorithms for Discovery and Identification of Pathogens Using RNA-Seq // PLoS One : журнал. — 2013. — Т. 8, вып. 10. — PMID 24204709.
  4. ↑ 1 2 Li Heng, Homer Nils. A survey of sequence alignment algorithms for next-generation sequencing // Brief Bioinformatics : журнал. — 2010. — Сентябрь (т. 11, вып. 5). — С. 473—483. — doi:10.1093/bib/bbq015. — PMID 20460430. Архивировано 15 апреля 2017 года.
  5. ↑ Jing Shang, Fei Zhu, Wanwipa Vongsangnak, Yifei Tang, Wenyu Zhang, Bairong Shen. Evaluation and Comparison of Multiple Aligners for Next-Generation Sequencing Data Analysis // Brief Bioinformatics : журнал. — 2010. — Сентябрь (т. 11, вып. 5). — С. 1754—1760. — PMID 24779008.
  6. ↑ Large Whole-Genome Sequencing (англ.). Illumina. Архивировано 30 января 2016 года.
  7. ↑ 1 2 Li Heng, Durbin Richard. Fast and accurate long-read alignment with Burrows-Wheeler transform (англ.) // Bioinformatics : журнал. — Oxford University Press, 2010. — 1 March (vol. 26, iss. 5). — P. 589—595. — ISSN 1367-4803. — doi:10.1093/bioinformatics/btp698. — PMID 20080505. Архивировано 5 апреля 2017 года.
  8. ↑ 1 2 3 4 Manual Reference Pages - bwa (англ.). SouceForge. Дата обращения: 5 апреля 2017. Архивировано из оригинала 5 апреля 2017 года.
  9. ↑ Heng Li's Homepage (англ.). SourceForge. Дата обращения: 6 апреля 2017. Архивировано из оригинала 6 апреля 2017 года.
  10. ↑ 1 2 Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM. Compressed indexing and local alignment of DNA (англ.) // Bioinformatics : журнал. — Oxford University Press, 2008. — 15 March (vol. 24, iss. 6). — P. 791—797. — ISSN 1367-4803. — doi:10.1093/bioinformatics/btn032. — PMID 18227115. Архивировано 5 апреля 2017 года.
  11. ↑ Sohyun Hwang, Eiru Kim, Insuk Lee, Edward M. Marcotteb. Systematic comparison of variant calling pipelines using gold standard personal exome variants (англ.) // Scientific Reports : онлайн-журнал. — Macmillan Publishers Limited, 2015. — Iss. 5. — ISSN 2045-2322. — doi:10.1038/srep17875. Архивировано 5 апреля 2017 года.
  12. ↑ Pareek C. S., Błaszczyk P., Dziuba P., Czarnik U., Fraser L., Sobiech P., Pierzchała M., Feng Y., Kadarmideen H. N., Kumar D. Single nucleotide polymorphism discovery in bovine liver using RNA-seq technology // PLoS One : журнал. — 2017. — Февраль (т. 12, вып. 2). — doi:10.1371/journal.pone.0172687. — PMID 28234981. Архивировано 15 апреля 2017 года.
  13. ↑ Robinson K. M., Crabtree J., Mattick J. S., Anderson K. E., Dunning Hotopp J. C. Distinguishing potential bacteria-tumor associations from contamination in a secondary data analysis of public cancer genome sequence data // Microbiome : журнал. — Лондон, Великобритания: BioMed Central, 2017. — Январь (т. 5, вып. 1). — ISSN 2049-2618. — PMID 28118849. Архивировано 5 апреля 2017 года.
  14. ↑ Li Heng, Durbin Richard. Fast and accurate short read alignment with Burrows-Wheeler transform (англ.) // Bioinformatics : журнал. — Oxford University Press, 2009. — 15 July (vol. 25, iss. 14). — P. 1754—1760. — ISSN 1367-4803. — doi:10.1093/bioinformatics/btp324. — PMID 19451168. Архивировано 5 апреля 2017 года.
  15. ↑ Al-Absi A. A., Kang D. K. Long Read Alignment with Parallel MapReduce Cloud Platform // BioMed Research International : журнал. — Египет: Хиндави, 2015. — Декабрь. — ISSN 2314-6133. — doi:10.1155/2015/807407. — PMID 26839887. Архивировано 5 апреля 2017 года.
  16. ↑ Li Heng. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM (англ.). — Кембридж, США: Oxford University Press, 2016. — 16 March. — P. 1—3. — arXiv:1303.3997. Архивировано 5 апреля 2017 года.
  17. ↑ Peter J. A. Cock, Christopher J. Fields, Naohisa Goto, Michael L. Heuer, Peter M, Rice. The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants (англ.) // Nuclear Acid Res : журнал. — 2010. — April (vol. 38, iss. 6). — P. 1767—1771. — doi:10.1093/nar/gkp1137. — PMID 20015970. Архивировано 15 апреля 2017 года.
  18. ↑ BWA Usage (англ.). Голландский вычислительный центр. Архивировано из оригинала 5 апреля 2017 года.
  19. ↑ 1 2 Bukowski Robert, Sun Qi, Wang Minghui. Variant calling. — Bioinformatics Facility, Institute of Biotechnology. — С. 22. Архивировано 6 апреля 2017 года.
  20. ↑ The SAM/BAM Format Specification Working Group. Sequence Alignment/Map Format Specification (англ.) С. 3. GitHub (28 апреля 2016). Дата обращения: 6 апреля 2017. Архивировано из оригинала 6 апреля 2017 года.
  21. ↑ José M. Abuín, Juan C. Pichel, Tomás F. Pena, Jorge Amigo. SparkBWA: Speeding Up the Alignment of High-Throughput DNA Sequencing Data (англ.) // PLoS One : журнал. — 2016. — Vol. 11, iss. 5. — doi:10.1371/journal.pone.0155461. Архивировано 5 апреля 2017 года.
  22. ↑ Justin Chu, Sara Sadeghi, Anthony Raymond, Shaun D. Jackman, Ka Ming Nip, Richard Mar, Hamid Mohamadi, Yaron S. Butterfield, A. Gordon Robertson, Inanç Birol. BioBloom tools: fast, accurate and memory-efficient host species sequence screening using bloom filters (англ.) // Bioinformatics : журнал. — 2014. — 1 December (vol. 30, iss. 23). — P. 3402—3404. — doi:10.1093/bioinformatics/btu558. Архивировано 15 апреля 2017 года.
  23. ↑ David Weese, Manuel Holtgrewe, Knut Reinert. RazerS 3: Faster, fully sensitive read mapping (англ.) // Bioinformatics : журнал. — Oxford University Press, 2012. — 15 October (vol. 28, iss. 20). — P. 2592—2599. — ISSN 1367-4803. — doi:10.1093/bioinformatics/bts505. — PMID 22923295. Архивировано 6 апреля 2017 года.
  24. ↑ Barh Debmalya, Khan Muhammad Sarwar, Davies Eric. PlantOmics: The Omics of Plant Science. — Springer, 2015. — С. 56. — 825 с. — ISBN 8132221729. — ISBN 9788132221722. Архивировано 6 апреля 2017 года.
  25. ↑ Julio Saez-Rodriguez, Miguel P. Rocha, Florentino Fdez-Riverola, Juan F. De Paz Santana. 8th International Conference on Practical Applications of Computational Biology & Bioinformatics (PACBB 2014). — Springer, 2014. — Т. 294. — С. 114. — 294 с. — ISBN 3319075810. — ISBN 9783319075815. Архивировано 6 апреля 2017 года.
  26. ↑ Gerton Lunter. Notes for Stampy v1.0.20 (англ.). Оксфорд, Великобритания: Trust Centre for Human Genetics (сентябрь 2012). Дата обращения: 6 апреля 2017. Архивировано из оригинала 6 апреля 2017 года.
  27. ↑ Elsensohn MH., Leblay N., Dimassi S., Campan-Fournier A., Labalme A., Roucher-Boulez F., Sanlaville D., Lesca G., Bardel C., Roy P. Statistical method to compare massive parallel sequencing pipelines (англ.) // BMC Bioinformatics : журнал. — Лондон, Великобритания: BioMed Central, 2017. — 1 March (vol. 18, iss. 1). — P. 139. — ISSN 1471-2105. — doi:10.1186/s12859-017-1552-9. Архивировано 5 апреля 2017 года.
  28. ↑ GATK Best Practices (англ.). Broad Institute. Дата обращения: 5 апреля 2017. Архивировано из оригинала 5 апреля 2017 года.
  29. ↑ Pevsner Jonathan. Bioinformatics and Functional Genomics. — 3-е изд. — John Wiley & Sons, 2015. — С. 401. — 1160 с. — ISBN 9781118581698. — ISBN 1118581695. Архивировано 6 апреля 2017 года.
  30. ↑ Ishii K., Kazama Y., Hirano T., Hamada M., Ono Y., Yamada M., Abe T. AMAP: A pipeline for whole-genome mutation detection in Arabidopsis thaliana (англ.) // Genes Genet Syst : журнал. — The Genetics Society of Japan, 2017. — 17 March (vol. 91, iss. 4). — P. 229—233. — ISSN 1341-7568. — doi:10.1266/ggs.15-00078. — PMID 27452041. Архивировано 5 апреля 2017 года.
  31. ↑ SPAdes 3.10.1 Manual (англ.). Санкт-Петербургский академический университет — научно-образовательный центр нанотехнологий РАН. Дата обращения: 5 апреля 2017. Архивировано из оригинала 5 апреля 2017 года.

Литература править

Источник — https://ru.wikipedia.org/w/index.php?title=BWA_(выравнивание_биологических_последовательностей)&oldid=133708287