March 18, 2014, 8:26 p.m. by Rosalind Team
We are now ready to describe BWMATCHING, an algorithm that counts the total number of matches of Pattern in Text, where the only information that we are given is FirstColumn and LastColumn = BWT(Text) in addition to the Last-to-First mapping (from “Generate the Last-to-First Mapping of a String”). The pointers top and bottom are updated by the green lines in the following pseudocode.
Given: A string BWT(Text), followed by a collection of strings Patterns.
Return: A list of integers, where the i-th integer corresponds to the number of substring matches of the i-th member of Patterns in Text.
TCCTCTATGAGATCCTATTCTATGAAACCTTCA$GACCAAAATTCTCCGGC CCT CAC GAG CAG ATC
2 1 1 0 1