Question: BWA MEM Algorithm
1
3.6 years ago by
France
arunnatrajanravi30 wrote:

Hi everyone,

I would like to understand how the algorithm behind BWA MEM works... So, I tried reading the papers on NCBI about BWA MEM and I even saw the posters about this but, I still can't understand completely how it works... Can someone explain it to me with some simple words?

Regards,

next-gen alignment • 12k views
modified 2.9 years ago by shivani9674520 • written 3.6 years ago by arunnatrajanravi30

How what works, exactly? The Burrows-Wheeler transformation? Mapping in general? BWA? The MEM algorithm?

Thank you for your answer. Yes, I would like to know how it works in general. So, BWA Mapping in general and the MEM algorithm....

Regards

6
3.6 years ago by
mark.ziemann1.1k
Australia/Mebourne/Geelong/Deakin
mark.ziemann1.1k wrote:

Here's an intro to BWT for bioinformatics from Stanford Uni.

http://web.stanford.edu/class/cs262/presentations/lecture4.pdf

5
2.9 years ago by

Hi!

I will risk to post the obsolete answer.

BWA execution from the high level can be observed as creating indexing structures (run bwa index which outputs 5 index files) out of sub-sequences of the reference genome (fasta file) in order to enable search of the sequence w from input reads (fastq format) in constant complexity - O(|w|). Indexing is based on the Burrows-Wheeler transformation (Google video with explanation of BWT and the interview with Mike Burrows https://youtu.be/4WRANhDiSHM?) and FM index https://en.wikipedia.org/wiki/FM-index.

After watching mentioned video and reading wiki you will be ready for the final treat, the BWA MEM paper from its author Heng Li: http://arxiv.org/abs/1303.3997

2
3.5 years ago by
France
arunnatrajanravi30 wrote:

Hi Mark,

It doesn't explain BWA MEM algorithm. It sure helps to understand the basic concept BWA.

http://arxiv.org/abs/1303.3997

I am not able to understand everypart of this paper.

Regards,

What exactly do you don't understand?