SORA

SORA implements scalable string-graph reduction algorithms to perform parallel reduction of large overlap graphs for de novo genome assembly.

Key Features:

• Scalability: Implements Apache Spark–based processing to handle massive as well as mid-to-small overlap graphs with linear-scaling behavior as computational resources increase.
• Graph Reduction Efficiency: Uses graph reduction to compact overlap/string graphs by reducing the number of edges in large graph paths to lower computational overhead.
• Graph Processing Libraries: Employs Spark graph processing libraries such as GraphX and GraphFrames for scalable graph computations.
• Computational Environments: Operates on both single machines and distributed cloud clusters leveraging parallel computation.
• Performance on Large Datasets: Demonstrated capability on human genome samples, including processing nearly one billion-edge graphs in a distributed cloud environment while also handling mid-to-small graphs on individual workstations.
• Sequencing Data Compatibility: Targets memory-intensive datasets from next-generation sequencing and third-generation long reads by optimizing graph processing.

Scientific Applications:

• De novo genome assembly: Enables reconstruction of genomes from overlapping genomic fragments without relying on reference sequences by improving overlap-graph reduction scalability and efficiency.

Methodology:

SORA leverages Apache Spark and Spark graph libraries (GraphX, GraphFrames) to implement scalable string-graph reduction algorithms, optimizing parallel graph processing to mitigate memory-intensive challenges from next-generation sequencing and third-generation long reads.