Minimum-WDFA-Constructor

This software implements an algorithm that computes the minimum Wheeler deterministic finite automaton (WDFA) equivalent to a given minimum DFA of a Wheeler language.

Requirements

• C++20 compiler (tested with Clang and GCC)
• 64-bit Linux or macOS operating system

External Dependencies

This project depends on the following external libraries:

• DYNAMIC — succinct dynamic data structures
• hopscotch-map — fast hash map implementation

Setup

Clone this repository:

git clone https://github.com/regindex/Minimum-WDFA-Constructor.git
cd Minimum-WDFA-Constructor

Clone the dependencies:

git submodule update --init --recursive

Build the project:

# standard build
make
# compile enabling AVX instructions
make AVX=on

Usage

./minWDFA input.bin

Tests

Pipeline for running tests on https://www.cs.helsinki.fi/group/gsa/1000gen-FIN-WholeGenome/ datataset

cd tools
g++ -std=c++17 -O3 dfa2bin.cpp -o dfa2bin
cd wdfa2mdfa/
g++ -std=c++17 -O3 Modified.cpp -o minimizer
cd ../read-fin-automaton
g++ -std=c++17 -O3 read-fin-automaton.cpp -o read-fin-automaton
mkdir automata
./script_test_fin-automata

Pipeline for running gcsa tests on https://www.cs.helsinki.fi/group/gsa/1000gen-FIN-WholeGenome/ datataset

cd benchmarks
python3 configure.py --build 
# construct the pangenome automata
python3 experiments_script.py --build_automata
# construct the gcsa indexes and collect performance
python3 experiments_script.py --build_gcsa