DIDA

DIDA is a novel framework that performs the large-scale alignment tasks by distributing the indexing and alignment stages into smaller subtasks over a cluster of compute nodes.

Project Description

One of the most essential applications in bioinformatics affected by High-Throughput Sequencing (HTS) data deluge is the sequence alignment problem where nucleotide or amino acid sequences are queried against targets to find regions of close similarity. When queries are too many and/or targets are too large the alignment problem becomes a computationally challenging problem. This is especially true when targets are dynamic such as intermediate steps of a de novo assembly process. To address this problem, we have designed and developed DIDA, a distributed and parallel indexing and alignment algorithm. First, we partition the targets into smaller parts using a heuristic balanced cut. Next, we create an index for each partition. The reads are then “flowed” through a Bloom filter to dispatch the alignment task to the corresponding node(s). Finally, the reads are aligned on all partitions and the results are combined together to create the final output.

Citation

Mohamadi H, Vandervalk BP, Raymond A, Jackman SD, Chu J, et al. (2015) DIDA: Distributed Indexing Dispatched Alignment. PLoS ONE 10(4): e0126409. doi: 10.1371/journal.pone.0126409