RLZ-Graph

RLZ-Graph constructs space-efficient genome graphs by compressing input genomic sequences using the relative Lempel-Ziv (RLZ) algorithm and transforming graphs into external pointer macro (EPM)-compressed forms. It reduces storage requirements for genome graphs derived from .fasta sequences.

Key Features:

• RLZ-Based Sequence Compression: Compresses genomic sequences using the relative Lempel-Ziv algorithm to minimize node labels and edge storage in genome graphs.
• EPM Graph Transformation: Applies linear-time algorithms to convert genome graphs into EPM-compressed representations with provable upper bounds on graph size.
• Source Assignment Optimization: Solves the source assignment problem using an integer linear programming (ILP) formulation to minimize graph size.

Scientific Applications:

• Large-Scale Genome Graph Construction: Enables compact storage and improved computational efficiency for genome graph-based analyses and sequence alignment in large genomic datasets.

Methodology:

RLZ-Graph compresses .fasta input sequences using RLZ, encodes genome graphs under the EPM compression model via linear-time transformations, and applies ILP-based source assignment optimization to achieve minimal graph representations.