Burrows-Wheeler Alignment Part 1

Consider the following problem of read alignment. You are given millions of small pieces of DNA sequence, called reads and one large DNA sequence called the reference sequence (DNA sequences contain only 4 letters A, C, G, T representing the four bases). You have to find how many of those... [Read More]

Burrows-Wheeler Transform

Burrows-Wheeler transform (or, BWT) is a block compression algorithm and is used in programs like bzip. The output of the algorithm is a string which contains chunks of same characters which can be easily stored in a compact form. The compression is lossless, that is, we can get back the... [Read More]

Programming Gale-Shapley Algorithm in C++

We will be writing program for Gale-Shapley Algorithm in C++. This algorithm is used to solve the Stable Marriage Problem. You can get the problem on SPOJ, or on codechef. You can understand the algorithm from Gale-Shapley’s paper: College Admissions and the Stability of Marriage [Read More]