Methods - FastHASH


Adjacency Filtering

Adjacency Filtering (AF) can quickly check if a mapping location is valid or not without performing the costly edit-distance calculation.

The key idea of Adjacency Filtering is simple: a potential mapping location of the read is valid only when most K-mers of the read can find a close-by location in their corresponding location lists.

To better illustrate the key idea of Adjacency Filtering, let's take a look at an example.


In this example, a read, "ACTCGGCTACTGGCCTAATACCTGACGGGGATACTGGTACAGTCGTCCATCGGACTTTAGGCCCAACCGTAGGCTTAGGCTAGCG", is being mapped to the human reference (hg19_v37) under an error threshold of 2 bps (base-pairs). The read is broken into 7 K-mers with K=12 (or simply 12-mers). A potential mapping location "m" from the location list of the first K-mer "ACTCGGCTACTG" is proposed by the mapper as a potential mapping site of the read.

We know "m" is indeed a correct mapping site of this read because there is only a single bp difference between the read and the reference at "m" (an insertion in the 6th K-mer). However, the mapper only knows this after it has calculated the edit-distance between the read and the reference at "m". This edit-distance calculation is costly When the potential mapping location corresponds a correct mapping (the target reference differs from the read by no more than e errors), like in the example above, then most K-mers of the read should be able to find a location relatively close to


Cheap K-mer Selection

Wix also offers a ton of free design elements right inside the editor, like images, icons, galleries, videos and large selection of Add Ons and social feeds.