Fractal MapReduce decomposition of sequence alignment

Fractal MapReduce decomposition of sequence alignment

2012 | Jonas S Almeida1*, Alexander Grüneberg1,2, Wolfgang Maass2,3 and Susana Vinga4,5
The report describes a novel approach to sequence alignment using iterated maps and fractal analysis, which provides an "alignment-free" solution. This method, based on the Chaos Game Representation (CGR) and Universal Sequence Map (USM), allows for the comparison of sequences without relying on dynamic programming. The key advantage is that it can be decomposed into multiple rounds of map and reduce operations, making it highly parallelizable and scalable. The procedure is implemented in JavaScript, leveraging the browser as a high-performance distributed computing environment. The accompanying webApp and open-source library (usm.js) enable users to perform sequence comparisons and alignments, demonstrating the practicality and efficiency of the method. The report highlights the potential of this approach for handling large genomic datasets and the broader applicability of the USM procedure to any sequence alphabet.The report describes a novel approach to sequence alignment using iterated maps and fractal analysis, which provides an "alignment-free" solution. This method, based on the Chaos Game Representation (CGR) and Universal Sequence Map (USM), allows for the comparison of sequences without relying on dynamic programming. The key advantage is that it can be decomposed into multiple rounds of map and reduce operations, making it highly parallelizable and scalable. The procedure is implemented in JavaScript, leveraging the browser as a high-performance distributed computing environment. The accompanying webApp and open-source library (usm.js) enable users to perform sequence comparisons and alignments, demonstrating the practicality and efficiency of the method. The report highlights the potential of this approach for handling large genomic datasets and the broader applicability of the USM procedure to any sequence alphabet.
Reach us at info@study.space
[slides and audio] Fractal MapReduce decomposition of sequence alignment