Genome Search

An integrated system for genomic sequence search, dependency-aware concurrent scheduling and relational data management, with a reproducible benchmarking framework.

System overview

Genome Search indexes, searches, stores and processes DNA and protein sequences. Algorithmic search, a workflow scheduler, a concurrent execution engine and a PostgreSQL store share one job model, so any component can be benchmarked in isolation or end to end.

A T G CDNA + protein sequences in — indexed, searched, stored & processed

Search algorithms

K-mer index & alignment

K-mer indexing, hash-table retrieval, trie prefix search and dynamic-programming alignment, each analysed for time and space complexity.

Workflow scheduler

Dependency graph

Jobs form a dependency graph. Topological sorting and a priority queue release independent tasks as soon as their inputs are ready.

Execution engine

Concurrent workers

Multi-process and multi-threaded workers with synchronization primitives, inter-process communication and controlled resource allocation.

Relational store

PostgreSQL schema

A normalized PostgreSQL schema for sequences, samples, jobs, execution metadata and results, with keys, constraints, transactions and indexes.

⇄ One shared job model — benchmark any stage in isolation or end to end

Complexity explorer

Input size n

Steps needed for each growth rate at the chosen n. Bars are on a logarithmic scale; the time column assumes 100 million simple steps per second.

Sequence search

A k-mer index moves the cost of searching from every query to a single build step. Lookup time stays flat as the reference grows, while a scan grows with it.

Query latency against reference size

Queries needed to repay the index build

Index memory

Choosing k: positions per k-mer

Prefix search over fixed-length sequences

Break-even explorer

Reference

Measure it on your device

Reference

Generates random DNA in your browser, then times a scan against a k-mer index, the same comparison as the chart on the left. Bars use a logarithmic scale.

Queries per second

Occurrences per k-mer

Seed sensitivity: does a k-mer survive mutation?

Why a trie stops branching

Effect of query length

Index memory against k

Hash table lookup cost

Memory added by each structure

Dynamic-programming alignment

Smith-Waterman local alignment fills an m by n matrix, so time grows with the product of the lengths. Keeping only two rows when the score alone is needed removes almost all of the memory cost.

Alignment time

Peak memory

Alignment explorer

Sequence ASequence B

Match Mismatch Gap

Traceback alignment

Score along the path

Score distribution by similarity

Matrix cells filled per second

Dependency-aware scheduling

Each workflow is a directed acyclic graph. The scheduler keeps ready tasks in a priority queue and starts the longest first, which shortens the finishing time on limited workers.

Benchmark workflow: 32 tasks across six stages

Edge lengths are not to scale. Each task’s duration was measured by running a real alignment of that stage’s size.

Schedule on 4 workers

Workers

Speedup against workers

Scheduler overhead against graph size

Where the time goes, by stage

Worker utilization

Priority queue cost

Scheduling policy

Relational storage and indexing

Metadata queries filter on sample and sequence properties. Indexes turn those scans into lookups, and the gap widens with every row added.

Filter by sample

Join with filter and aggregate

Write throughput

What the database does: query plans

samples(sample_id PK, name)
sequences(seq_id PK, sample_id FK, length, gc)
jobs(job_id PK, seq_id FK, task, priority, status)
executions(exec_id PK, job_id FK, started, finished, cpu_s, peak_mb)
results(result_id PK, job_id FK, seq_id FK, position, score)

Real example datasets

The workbench ships with real public-domain sequences in app/data (catalogued in datasets.json), selectable from the Data tab via “Real example”. Public-domain NCBI RefSeq records via the Biopython test suite; see bench_real.py for provenance.

Example datasets

Dataset	Accession	Sequences	Bases	GC
Arabidopsis thaliana chloroplast (full)	NC_000932.1	1	154,478	0.363
Chloroplast coding sequences (85 genes)	NC_000932.1-CDS	85	79,482	~0.37
Chloroplast 10 kb demo subset	NC_000932.1-demo	1	10,000	0.302
Yersinia pestis plasmid pPCP1 (full)	NC_005816.1	1	9,609	0.453

Tip: contrast the AT-rich chloroplast against the higher-GC plasmid in the workbench GC-against-length plot, or index the 10 kb subset for an instant search demo.

Run it yourself: workbench, notebooks and source

The charts above show measurements. The Streamlit workbench and the notebooks are the system itself: load your own FASTA, search it, align pairs, run a dependency graph on real workers, query the relational store and benchmark all of it on your own machine.

Data and search

Upload or generate sequences, build a k-mer index, and run exact, mismatch-tolerant or trie prefix searches with a hit map across every sequence.

Alignment

Local and global alignment with editable scores, a scoring-matrix heatmap with traceback, and a dot plot.

Workflow engine

Edit the task graph, break it with a cycle, then run it on threads or processes and see a real execution timeline with the critical path.

Database and benchmarks

Run SQL against the schema, read query plans, toggle indexes, and time every method live.

Get the code & run it

How the numbers were made

Every figure above comes from one small benchmark program that ran in a sandbox. Step through the program, inspect the sandbox, then see which results were measured directly and which were not.

The measurement pipeline

The sandbox

One core, many workers

Workers

Run-to-run variation

Provenance of every result

Publish your own measurements

To publish your own measurements, run python3 bench/bench.py > results.json, then python3 bench_extra.py and python3 bench_more.py from inside bench/, and paste the output into the <script id="data"> block of index.html. Every chart, caption and headline figure recomputes from that data.

Contact

Questions, data requests or feedback: harshinisuresha7@gmail.com