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

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

Интерактивная навигация по истории

[непроверенная версия]

[отпатрулированная версия]

← Предыдущая правка Следующая правка →

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Версия от 15:15, 5 апреля 2017

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

Для образцов 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].

История

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

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

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

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

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

BWA-BackTrack

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

BWA-SW

BWA-SW строит FM-индексы и для референсной последовательности и для чтений. Он неявно представляет собой референсную последовательность в виде префиксного дерева и чтения в виде детерминированного ациклического конечного автомата, который составляется из префиксного дерева для чтения с использованием динамического программирования. В отличие от BLAT и SSAHA2, BWA-SW находит сиды (от англ. seed — «семя»; точное совпадение нескольких пар оснований чтения^[14]) в референсном геноме с помощью построения FM-индексов. Выравнивание расширяется, когда сид имеет несколько вхождений в эталонной последовательности. Скорость достигается за счет уменьшения ненужного расширения для высоко повторяющихся последовательностей. По сравнению со стандартным выравниванием Смита — Ватермана временная сложность которого равна $O(|X|*|W|)$ , BWA-SW имеет лучшую временную сложность, так как он, как минимум, не медленнее, чем BWT-SW, сложность которого — $O(|X|*0,628*|W|)$ ^[9]. В BWA-SW два выравнивания считаются различными, если длина зоны перекрытия по запросу составляет менее половины длины более короткого сегмента запроса.

Реализация принимает индекс BWA и FASTA запроса или FASTQ файла в качестве входных данных и выводит выравнивание в формате SAM. Входной файл, как правило, содержит много последовательностей («ридов»). Каждая последовательность обрабатывается, в свою очередь, с использованием нескольких потоков, если это возможно. Использование памяти составляет около 3,7 Гб для генома человека. Требуемый объём памяти для каждого запроса примерно пропорционален длине последовательности. Кроме того, BWA-SW способен обнаружить химеру, потенциально вызванную структурными изменениями или эталонными ошибками сборки ридов, которые могут представлять угрозу для BLAT и SSAHA2. BWA-SW отличается от BWT-SW в нескольких аспектах. Во-первых, BWT-SW гарантирует, что найдёт все локальные совпадения, в то время как BWA-SW представляет собой эвристический алгоритм, который может пропустить истинные совпадения, но работает гораздо быстрее.

BWA-MEM

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

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

Для каждого выравнивания программный пакет BWA вычисляет оценку качества картирования — Phred масштабированную вероятность того, что выравнивание является некорректным^[8]. Необходимость статистической оценки картирования возникает из-за того, что риды получаются маленькие (40—100 п.о), а геномы достаточно большие, поэтому выравниваний может быть несколько. Тем не менее, необходимо понять, какое из них наиболее информативное. И по сути Phred-оценка представляет собой вероятность того, что рид выравнен неправильно. Вычисляется она по формуле $p=10^{-q/10}$ , где q — качество прочтения рида^[16]. Алгоритм аналогичен оценке для MAQ, за исключением того, что в BWA предполагается, что истинное совпадение всегда может быть найдено. Такое изменение было сделано в связи с тем, что формула MAQ переоценивает вероятность пропуска истинного совпадения, что приводит к заниженному качеству картирования. Моделирование показывает, что BWA может переоценивать качество картирования из-за этой модификации, но отклонение относительно невелико.

Примеры

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

Шаг 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. Сама read group для образца с платформы Illumina-SOLEXA выглядит примерно следующим образом: -r ‘@RG\tID:1\tSM:S000336\tPL:ILLUMINA\tLB:L00000336\t PU:C3A7NACXX:1’, где ID — это уникальный идентификатор данного образца, SM — это названия образца, Pl — это платформа для секвенирования, LB — название библиотеки, а PU — системный идентификатор.

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

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

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

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

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

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

GATK^[19]
AMAP^[20]
SPAdes^[21]

Примечания

↑ Heng Li. BWA Releases (англ.). GitHub. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.
↑ Гольцов А.Ю., Андреева Т.В., Решетов Д.А., Тяжелова Т.В., Гаврик О.А., Рогаев Е.И. Поиск мутаций в генах митохондриальной ДНК, ассоциированных с развитием болезни Альцгеймера, с использованием технологии параллельного секвенирования // Современные проблемы науки и образования : журнал. — М.: Российская академия естествознания, 2012. — № 6. — С. 23. — ISSN 1817-6321. Архивировано 5 апреля 2017 года.
↑ 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.
↑ Heng Li, Nils Homer. [ttp://www.ncbi.nlm.nih.gov/pmc/articles/PMC20460430/ PMC: 20460430 A survey of sequence alignment algorithms for next-generation sequencing] // Brief Bioinformatics : журнал. — 2010. — Сентябрь (т. 11, вып. 5). — С. 473-483. — PMID 20460430.
↑ 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.
↑ Large Whole-Genome Sequencing (англ.). Illumina. Архивировано 5 апреля 2017 года.
↑ 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 года.
↑ ¹ ² ³ Manual Reference Pages - bwa (англ.). SouceForge. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.
↑ ¹ ² 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 года.
↑ 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 года.]
↑ 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.
↑ 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 года.
↑ 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 года.
↑ Heng Li, Nils Homer. A survey of sequence alignment algorithms for next-generation sequencing // Brief Bioinformatics : журнал. — 2010. — Сентябрь (т. 11, вып. 5). — С. 473—483. — doi:10.1093/bib/bbq015. — PMID 20460430.
↑ Li Heng. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. — Кембридж, США: Oxford University Press, 2016. — 16 марта. — С. 1—3. — arXiv:1303.3997. Архивировано 5 апреля 2017 года.
↑ 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.
↑ BWA Usage (англ.). Голландский вычислительный центр. Архивировано 5 апреля 2017 года.
↑ 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 года.
↑ GATK Best Practices (англ.). Broad Institute. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.
↑ 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 года.
↑ SPAdes 3.10.1 Manual (англ.). Санкт-Петербургский академический университет — научно-образовательный центр нанотехнологий РАН. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.

[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] Heng Li, Nils Homer. [ttp://www.ncbi.nlm.nih.gov/pmc/articles/PMC20460430/ PMC: 20460430 A survey of sequence alignment algorithms for next-generation sequencing] // Brief Bioinformatics : журнал. — 2010. — Сентябрь (т. 11, вып. 5). — С. 473-483. — PMID 20460430.

[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. Архивировано 5 апреля 2017 года.

[7] 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 года.

[manual-8] ¹ ² ³ Manual Reference Pages - bwa (англ.). SouceForge. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.

[compressed-9] ¹ ² 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 года.

[10] 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 года.]

[11] 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.

[12] 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 года.

[13] 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 года.

[14] Heng Li, Nils Homer. 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] Li Heng. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. — Кембридж, США: Oxford University Press, 2016. — 16 марта. — С. 1—3. — arXiv:1303.3997. Архивировано 5 апреля 2017 года.

[16] 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.

[17] BWA Usage (англ.). Голландский вычислительный центр. Архивировано 5 апреля 2017 года.

[18] 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 года.

[19] GATK Best Practices (англ.). Broad Institute. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.

[20] 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 года.

[21] SPAdes 3.10.1 Manual (англ.). Санкт-Петербургский академический университет — научно-образовательный центр нанотехнологий РАН. Дата обращения: 5 апреля 2017. Архивировано 5 апреля 2017 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

@@ Строка 10: / Строка 10: @@
 |сайт= http://bio-bwa.sourceforge.net/
 }}
-'''BWA''' ({{lang-en|'''B'''urrows-'''W'''heeler '''A'''ligner}}) — программный пакет для [[Картирование коротких прочтений|картирования коротких прочтений]] на большие референсные геномы (такие как, например, геном человека<ref>{{статья |автор= Гольцов А.Ю., Андреева Т.В., Решетов Д.А., Тяжелова Т.В., Гаврик О.А., Рогаев Е.И. |заглавие= Поиск мутаций в генах митохондриальной ДНК, ассоциированных с развитием болезни Альцгеймера, с использованием технологии параллельного секвенирования |ссылка= http://online.rae.ru/1232 |издание= Современные проблемы науки и образования |тип= журнал |место= {{М}} |издательство= Российская академия естествознания |год= 2012 |том= |номер= 6 |страницы= 23 |issn= 1817-6321 |archiveurl= http://web.archive.org/web/20170405075019/http://online.rae.ru/1232 |archivedate= 2017-04-05}}</ref>), написанный китайским биоинформатиком [[:en:Heng Li|Хенг Ли]] и англичанином [[:en:Richard M. Durbin|Ричардом Дурбиным]]. Является одним из широкоиспользуемых алгоритмов выравнивания<ref>{{статья |автор=Ivan Borozan, Stuart N. Watt, Vincent Ferretti|заглавие=Evaluation of Alignment Algorithms for Discovery and Identification of Pathogens Using RNA-Seq|ссылка= http://www.ncbi.nlm.nih.gov/pmc/articles/PMC24204709/|издание= PLoS One|тип= журнал |место= {{М}} |год=2013 |том= 8 |выпуск= 10| pmid = 24204709}}</ref><ref>{{статья |автор=Heng Li, Nils Homer|заглавие=A survey of sequence alignment algorithms for next-generation sequencing|ссылка=ttp://www.ncbi.nlm.nih.gov/pmc/articles/PMC20460430/ PMC: 20460430 |издание= Brief Bioinformatics|тип= журнал |место= {{М}} |год=2010 |месяц= 9 |том= 11 |выпуск= 5|страницы= 473-483 | pmid = 20460430}}</ref><ref>{{статья |автор=Jing Shang, Fei Zhu, Wanwipa Vongsangnak, Yifei Tang, Wenyu Zhang, Bairong Shen|заглавие=Evaluation and Comparison of Multiple Aligners for Next-Generation Sequencing Data Analysis |ссылка= http://www.ncbi.nlm.nih.gov/pmc/articles/PMC24779008/ |издание= Brief Bioinformatics|тип= журнал |место= {{М}} |год=2010 |месяц= 9 |том= 11 |выпуск= 5|страницы= 1754—1760 | pmid = 24779008}}</ref>, а также рекомендуется для анализа данных производителями [[Illumina]]<ref>{{cite web|url= [http://www.illumina.com/content/illumina-marketing/amr/en_US/techniques/sequencing/dna-sequencing/whole-genome-sequencing/large-genomes.html |title= Large Whole-Genome Sequencing  |publisher= Illumina |lang= en }}</ref>. BWA состоит из трёх основных алгоритмов: BWA-BackTrack, BWA-SW и BWA-MEM. В основе алгоритмов BWA лежит [[Преобразование Барроуза — Уилера|преобразование Барроуза—Уилера]], [[Суффиксный массив|суффиксные массивы]] и [[Алгоритм Смита — Ватермана|алгоритм выравнивания Смита—Ватермана]]. Программный пакет умеет работать с длинными последовательностями на порядок быстрее, чем [http://maq.sourceforge.net/ MAQ] при достижении аналогичной точности выравнивания<ref>{{статья |автор= Li Heng, Durbin Richard |заглавие= Fast and accurate long-read alignment with Burrows-Wheeler transform |ссылка= https://academic.oup.com/bioinformatics/article/26/5/589/211735/Fast-and-accurate-long-read-alignment-with-Burrows |издание= Bioinformatics |тип= журнал |место= |издательство= Oxford University Press |год= 2010 |месяц= 3 |число= 1 |том= 26 |выпуск= 5 |страницы= 589—595 |issn= 1367-4803 |doi= 10.1093/bioinformatics/btp698 |pmid= 20080505 |язык= en |archiveurl= http://web.archive.org/web/20170405071105/https://academic.oup.com/bioinformatics/article/26/5/589/211735/Fast-and-accurate-long-read-alignment-with-Burrows |archivedate= 2017-04-05}}</ref>.
+'''BWA''' ({{lang-en|'''B'''urrows-'''W'''heeler '''A'''ligner}}) — программный пакет для [[Картирование коротких прочтений|картирования коротких прочтений]] на большие референсные геномы (такие как, например, геном человека<ref>{{статья |автор= Гольцов А.Ю., Андреева Т.В., Решетов Д.А., Тяжелова Т.В., Гаврик О.А., Рогаев Е.И. |заглавие= Поиск мутаций в генах митохондриальной ДНК, ассоциированных с развитием болезни Альцгеймера, с использованием технологии параллельного секвенирования |ссылка= http://online.rae.ru/1232 |издание= Современные проблемы науки и образования |тип= журнал |место= {{М}} |издательство= Российская академия естествознания |год= 2012 |том= |номер= 6 |страницы= 23 |issn= 1817-6321 |archiveurl= http://web.archive.org/web/20170405075019/http://online.rae.ru/1232 |archivedate= 2017-04-05}}</ref>), написанный китайским биоинформатиком [[:en:Heng Li|Хенг Ли]] и англичанином [[:en:Richard M. Durbin|Ричардом Дурбиным]]. Является одним из широкоиспользуемых алгоритмов выравнивания<ref>{{статья |автор=Ivan Borozan, Stuart N. Watt, Vincent Ferretti|заглавие=Evaluation of Alignment Algorithms for Discovery and Identification of Pathogens Using RNA-Seq|ссылка= http://www.ncbi.nlm.nih.gov/pmc/articles/PMC24204709/|издание= PLoS One|тип= журнал |год=2013 |том= 8 |выпуск= 10| pmid = 24204709}}</ref><ref>{{статья |автор=Heng Li, Nils Homer|заглавие=A survey of sequence alignment algorithms for next-generation sequencing|ссылка=ttp://www.ncbi.nlm.nih.gov/pmc/articles/PMC20460430/ PMC: 20460430 |издание= Brief Bioinformatics|тип= журнал |год=2010 |месяц= 9 |том= 11 |выпуск= 5|страницы= 473-483 | pmid = 20460430}}</ref><ref>{{статья |автор=Jing Shang, Fei Zhu, Wanwipa Vongsangnak, Yifei Tang, Wenyu Zhang, Bairong Shen|заглавие=Evaluation and Comparison of Multiple Aligners for Next-Generation Sequencing Data Analysis |ссылка= http://www.ncbi.nlm.nih.gov/pmc/articles/PMC24779008/ |издание= Brief Bioinformatics|тип= журнал |год=2010 |месяц= 9 |том= 11 |выпуск= 5|страницы= 1754—1760 | pmid= 24779008}}</ref>, а также рекомендуется для анализа данных производителями [[Illumina]]<ref>{{cite web|url= http://www.illumina.com/content/illumina-marketing/amr/en_US/techniques/sequencing/dna-sequencing/whole-genome-sequencing/large-genomes.html |title= Large Whole-Genome Sequencing |publisher= Illumina |lang= en |archiveurl= http://web.archive.org/save/_embed/https://www.illumina.com/techniques/sequencing/dna-sequencing/whole-genome-sequencing/large-genomes.html |archivedate= 2017-04-05}}</ref>. BWA состоит из трёх основных алгоритмов: BWA-BackTrack, BWA-SW и BWA-MEM. В основе алгоритмов BWA лежит [[Преобразование Барроуза — Уилера|преобразование Барроуза—Уилера]], [[Суффиксный массив|суффиксные массивы]] и [[Алгоритм Смита — Ватермана|алгоритм выравнивания Смита—Ватермана]]. Программный пакет умеет работать с длинными последовательностями на порядок быстрее, чем [http://maq.sourceforge.net/ MAQ] при достижении аналогичной точности выравнивания<ref>{{статья |автор= Li Heng, Durbin Richard |заглавие= Fast and accurate long-read alignment with Burrows-Wheeler transform |ссылка= https://academic.oup.com/bioinformatics/article/26/5/589/211735/Fast-and-accurate-long-read-alignment-with-Burrows |издание= Bioinformatics |тип= журнал |место= |издательство= Oxford University Press |год= 2010 |месяц= 3 |число= 1 |том= 26 |выпуск= 5 |страницы= 589—595 |issn= 1367-4803 |doi= 10.1093/bioinformatics/btp698 |pmid= 20080505 |язык= en |archiveurl= http://web.archive.org/web/20170405071105/https://academic.oup.com/bioinformatics/article/26/5/589/211735/Fast-and-accurate-long-read-alignment-with-Burrows |archivedate= 2017-04-05}}</ref>.
 Для образцов c платформ [[Метод Illumina/Solexa|Illumina-SOLEXA]], [[Пиросеквенирование|454 Life Sciences]], [[Ионное полупроводниковое секвенирование|ионного полупроводникового секвенирования]] или [[Метод Сэнгера|секвенирования по Сэнгеру]] с длиной чтений («ридов» от {{lang-en|read}} — «чтение, прочтение»; отдельные фрагменты ДНК, полученные в результате работы [[Методы секвенирования нового поколения|секвенатора]]) больше или равных 70 пар оснований (здесь и далее — п.о.), BWA-MEM обычно предпочтительней. BWA-MEM и BWA-SW имеют схожие функции, такие как, например, поддержка длинных прочтений. BWA-MEM имеет лучшую производительность, чем BWA-BackTrack для чтений, длиной 70—100 п.о. с платформы Illumina-SOLEXA.
@@ Строка 22: / Строка 22: @@
 == Использование ==
-Программный пакет BWA может быть использован в таких областях, как генотипирование для поиска [[Однонуклеотидный полиморфизм|однонуклеотидных полиморфизмов (снипов)]]<ref>{{статья |автор=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|ссылка= http://www.ncbi.nlm.nih.gov/pmc/articles/PMC28234981/|издание= PLoS One|тип= журнал |место= {{М}} |год=2017 | месяц= 2 |том= 12 |выпуск= 2| pmid = 28234981}}</ref>. Генотипирование позволяет проводить индивидуальное сравнение генотипов разных людей, с помощью него можно предсказывать предрасположенность людей к всевозможным заболеваниям, таким как рак, диабет и многие другие. Так же пакет будет полезен в [[транскриптом]]ике<ref>{{статья |автор=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|ссылка= http://www.ncbi.nlm.nih.gov/pmc/articles/PMC28118849/|издание= Microbiome|тип= журнал |место= {{М}} |год=2017 | месяц= 1 |том= 5 |выпуск= 1| pmid = 28118849}}</ref>.
+Программный пакет BWA может быть использован в таких областях, как генотипирование для поиска [[Однонуклеотидный полиморфизм|однонуклеотидных полиморфизмов (снипов)]]<ref>{{статья |автор=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|ссылка= https://www.ncbi.nlm.nih.gov/pubmed/28234981 |издание= PLoS One|тип= журнал |год=2017 | месяц= 2 |том= 12 |выпуск= 2|doi= 10.1371/journal.pone.0172687 |pmid= 28234981}}</ref>. Генотипирование позволяет проводить индивидуальное сравнение генотипов разных людей, с помощью него можно предсказывать предрасположенность людей к всевозможным заболеваниям, таким как рак, диабет и многие другие. Так же пакет будет полезен в [[транскриптом]]ике<ref>{{статья |автор=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|ссылка= https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5264480/ |издание= Microbiome |издательство= BioMed Central |тип= журнал |место= Лондон, Великобритания |год=2017 | месяц= 1 |том= 5 |выпуск= 1| pmid = 28118849 |archiveurl= http://archive.is/mAAvf |archivedate= 2017-04-05 |issn= 2049-2618 }}</ref>.
 Начиная с версии 0.6.x, все алгоритмы могут работать с геномами, общая длина которых больше 4 Гб<ref name="manual"/>. Тем не менее, размер индивидуальной хромосомы не должен превышать 2 Гб. Каждый алгоритм вызывается отдельной командой, принимает входной файл через стандартный поток ввода («stdin») и возвращает результат через стандартный поток вывода («stdout»).
@@ Строка 30: / Строка 30: @@
 === BWA-SW ===
-BWA-SW строит FM-индексы и для референсной последовательности и для чтений. Он неявно представляет собой референсную последовательность в виде [[Префиксное дерево|префиксного дерева]] и чтения в виде [[Конечный автомат|детерминированного ациклического конечного автомата]], который составляется из префиксного дерева для чтения с использованием [[Динамическое программирование|динамического программирования]]. В отличие от BLAT и SSAHA2, BWA-SW находит сиды (от {{lang-en|seed}} — «семя»; точное совпадение нескольких пар оснований чтения<ref>{{статья |автор=Heng Li, Nils Homer|заглавие=A survey of sequence alignment algorithms for next-generation sequencing|ссылка=ttp://www.ncbi.nlm.nih.gov/pmc/articles/PMC20460430/ PMC: 20460430 |издание= Brief Bioinformatics|тип= журнал |место= {{М}} |год=2010 |месяц= 9 |том= 11 |выпуск= 5|страницы= 473-483 | pmid = 20460430}}</ref>) в референсном геноме с помощью построения FM-индексов. Выравнивание расширяется, когда сид имеет несколько вхождений в эталонной последовательности. Скорость достигается за счет уменьшения ненужного расширения для высоко повторяющихся последовательностей. По сравнению со стандартным выравниванием Смита — Ватермана временная сложность которого равна <math> O(|X|*|W|) </math>, BWA-SW имеет лучшую временную сложность, так как он, как минимум, не медленнее, чем BWT-SW, сложность которого — <math> O(|X|*0,628*|W|) </math> <ref name="compressed">{{статья |автор= Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM |заглавие= Compressed indexing and local alignment of DNA |ссылка= https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btn032 |издание= Bioinformatics |тип= журнал |издательство= Oxford University Press |год= 2008 |месяц= 3|число=15 |том= 24|выпуск= 6 |страницы= 791—797 |issn= 1367-4803 |doi= 10.1093/bioinformatics/btn032 |pmid= 18227115 |язык= en|archiveurl= http://web.archive.org/web/20170405092017/https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btn032 |archivedate= 2017-04-05}}</ref>. В BWA-SW два выравнивания считаются различными, если длина зоны перекрытия по запросу составляет менее половины длины более короткого сегмента запроса.
+BWA-SW строит FM-индексы и для референсной последовательности и для чтений. Он неявно представляет собой референсную последовательность в виде [[Префиксное дерево|префиксного дерева]] и чтения в виде [[Конечный автомат|детерминированного ациклического конечного автомата]], который составляется из префиксного дерева для чтения с использованием [[Динамическое программирование|динамического программирования]]. В отличие от BLAT и SSAHA2, BWA-SW находит сиды (от {{lang-en|seed}} — «семя»; точное совпадение нескольких пар оснований чтения<ref>{{статья |автор=Heng Li, Nils Homer|заглавие=A survey of sequence alignment algorithms for next-generation sequencing|ссылка= https://www.ncbi.nlm.nih.gov/pubmed/20460430 |издание= Brief Bioinformatics|тип= журнал |год=2010 |месяц= 9 |том= 11 |выпуск= 5|страницы= 473—483 |doi= 10.1093/bib/bbq015 | pmid = 20460430}}</ref>) в референсном геноме с помощью построения FM-индексов. Выравнивание расширяется, когда сид имеет несколько вхождений в эталонной последовательности. Скорость достигается за счет уменьшения ненужного расширения для высоко повторяющихся последовательностей. По сравнению со стандартным выравниванием Смита — Ватермана временная сложность которого равна <math> O(|X|*|W|) </math>, BWA-SW имеет лучшую временную сложность, так как он, как минимум, не медленнее, чем BWT-SW, сложность которого — <math> O(|X|*0,628*|W|) </math> <ref name="compressed">{{статья |автор= Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM |заглавие= Compressed indexing and local alignment of DNA |ссылка= https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btn032 |издание= Bioinformatics |тип= журнал |издательство= Oxford University Press |год= 2008 |месяц= 3|число=15 |том= 24|выпуск= 6 |страницы= 791—797 |issn= 1367-4803 |doi= 10.1093/bioinformatics/btn032 |pmid= 18227115 |язык= en|archiveurl= http://web.archive.org/web/20170405092017/https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btn032 |archivedate= 2017-04-05}}</ref>. В BWA-SW два выравнивания считаются различными, если длина зоны перекрытия по запросу составляет менее половины длины более короткого сегмента запроса.
 Реализация принимает индекс BWA и FASTA запроса или FASTQ файла в качестве входных данных и выводит выравнивание в формате SAM. Входной файл, как правило, содержит много последовательностей («ридов»). Каждая последовательность обрабатывается, в свою очередь, с использованием нескольких потоков, если это возможно. Использование памяти составляет около 3,7 Гб для генома человека. Требуемый объём памяти для каждого запроса примерно пропорционален длине последовательности. Кроме того, BWA-SW способен обнаружить химеру, потенциально вызванную структурными изменениями или эталонными ошибками сборки ридов, которые могут представлять угрозу для BLAT и SSAHA2. BWA-SW отличается от BWT-SW в нескольких аспектах. Во-первых, BWT-SW гарантирует, что найдёт все локальные совпадения, в то время как BWA-SW представляет собой эвристический алгоритм, который может пропустить истинные совпадения, но работает гораздо быстрее.
@@ Строка 38: / Строка 38: @@
 == Показатели качества ==
-Для каждого выравнивания BWA вычисляет оценку качества картирования — Phred масштабированная вероятность того, что выравнивание является некорректным<ref name="manual"/>. Необходимость статистической оценки картирования возникает из-за того, что риды получаются маленькие (40 100 п.о), а геномы достаточно большие, поэтому выравниваний может быть несколько, но необходимо понять, какое из них наиболее информативное. И по сути Phred-оценка - вероятность того, что рид выравнен неправильно. Вычисляется он по формуле <math> p = 10^{-q/10} </math>, где q - качество прочтения рида<ref>{{статья |автор= 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 |ссылка= https://www.ncbi.nlm.nih.gov/pmc/articles/PMC20015970/ |издание= Nuclear Acid Res |тип= журнал |год= 2010 |месяц= 4 |том= 38|выпуск= 6 |страницы= 1767—1771 |doi= 10.1093/nar/gkp1137|pmid= 20015970 |язык= en}}</ref>. Алгоритм аналогичен оценке для [http://maq.sourceforge.net/qual.shtml MAQ], за исключением того, что в BWA предполагается, что истинное совпадение всегда может быть найдено. Такое изменение было сделано в связи с тем, что формула MAQ переоценивает вероятность пропуска истинного совпадения, что приводит к заниженному качеству картирования. Моделирование показывает, что BWA может переоценивать качество картирования из-за этой модификации, но отклонение относительно невелико.
+Для каждого выравнивания программный пакет BWA вычисляет оценку качества картирования — Phred масштабированную вероятность того, что выравнивание является некорректным<ref name="manual"/>. Необходимость статистической оценки картирования возникает из-за того, что риды получаются маленькие (40—100 п.о), а геномы достаточно большие, поэтому выравниваний может быть несколько. Тем не менее, необходимо понять, какое из них наиболее информативное. И по сути Phred-оценка представляет собой вероятность того, что рид выравнен неправильно. Вычисляется она по формуле <math> p = 10^{-q/10} </math>, где q — качество прочтения рида<ref>{{статья |автор= 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 |ссылка= https://www.ncbi.nlm.nih.gov/pubmed/20015970 |издание= Nuclear Acid Res |тип= журнал |год= 2010 |месяц= 4 |том= 38|выпуск= 6 |страницы= 1767—1771 |doi= 10.1093/nar/gkp1137 |pmid= 20015970 |язык= en}}</ref>. Алгоритм аналогичен оценке для [http://maq.sourceforge.net/qual.shtml MAQ], за исключением того, что в BWA предполагается, что истинное совпадение всегда может быть найдено. Такое изменение было сделано в связи с тем, что формула MAQ переоценивает вероятность пропуска истинного совпадения, что приводит к заниженному качеству картирования. Моделирование показывает, что BWA может переоценивать качество картирования из-за этой модификации, но отклонение относительно невелико.
+== Примеры ==
+Пример сценария использования программного пакета BWA от Голландского вычислительного центра выглядит следующим образом<ref>{{cite web|url=https://hcc-docs.unl.edu/display/HCCDOC/Running+BWA+Commands |title= BWA Usage |publisher= Голландский вычислительный центр |lang= en |archiveurl= http://web.archive.org/web/20170405151148/https://hcc-docs.unl.edu/display/HCCDOC/Running+BWA+Commands |archivedate= 2017-04-05}}</ref>:
-== Примеры<ref>{{cite web|url=https://hcc-docs.unl.edu/display/HCCDOC/Running+BWA+Commands |title= BWA Usage |publisher= Holland Computing Center |lang= en }}</ref> ==
 ;Шаг 1 — индексирование генома (∼3 CPU часа для генома человека):
 : <code>bwa index -a bwtsw ref.fa</code>
@@ Строка 56: / Строка 58: @@
 : <code>bwa bwasw ref.fa long-read.fq.gz > aln-long.sam</code>
 ,где long-read.fq.gz — файл с длинными чтениями.
 Для дальнейшей совместимости полученного выравнивания со стандартными программами для анализа NGS данных, таких как Pikard Tools, GATK при вызове программы следуют указывать так называемую read group добавлением флага -r. Сама read group для образца с платформы Illumina-SOLEXA выглядит примерно следующим образом: <code>-r ‘@RG\tID:1\tSM:S000336\tPL:ILLUMINA\tLB:L00000336\t PU:C3A7NACXX:1’</code>, где ID — это уникальный идентификатор данного образца, SM — это названия образца, Pl — это платформа для секвенирования, LB — название библиотеки, а PU — системный идентификатор.