This is a test version of Biostars. For the public version, visit https://www.biostars.org.
BWA MEM Algorithm

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,

alignment next-gen
• 28,869 views • link
updated by shivani967452 • shivani967452 • written by arunnatrajanravi • arunnatrajanravi

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

• 0 views • link
written by Brice Sarver Brice Sarver

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

• 0 views • link
written by arunnatrajanravi • arunnatrajanravi

3 answers

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) 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

Hope this was helpful,
Vladimir Kovacevic

• 0 views • link
updated by Ram Ram • written by vladimir.kovacevic vladimir.kovacevic

Here's an intro to BWT for bioinformatics from Stanford Uni: http://web.stanford.edu/class/cs262/presentations/lecture4.pdf

• 0 views • link
updated by Ram Ram • written by mark.ziemann mark.ziemann

Hi Mark,

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

But I found this article:

http://arxiv.org/abs/1303.3997

I am not able to understand everypart of this paper.

Regards,

• 0 views • link
written by arunnatrajanravi • arunnatrajanravi

What exactly do you don't understand?

• 0 views • link
written by scchess scchess

Thank you for your question. I do understand the basic concept of BWA. But, What makes BWA-MEM very special because nowadays everyone is using it. And how it works? Can someone explain it to me with some simple words?

• 0 views • link
written by arunnatrajanravi • arunnatrajanravi

Log in to answer this question.

More posts like this