BIOINFORMATICS · FEATURE ENGINEERING · COMPUTE ECONOMICS

A sequence is short to store—but some of its features are expensive to rediscover.

This lab follows DNA, RNA and protein sequences through composition, k-mers, alignment, structure and learned embeddings. Students calculate both algorithmic complexity and operational cost, then design a feature store that reuses evidence without losing provenance.

Explore common features →Estimate computation time ↓

Represent

Choose features that preserve useful biological signal.

Cost

Connect sequence length and dataset size to runtime.

Reuse

Avoid recomputing deterministic evidence for every model.

Trace

Version tools, databases, parameters and sequence identity.

01 · COMMON FEATURE LANDSCAPE

The closer a feature moves toward structure and context, the more computation it usually demands.

No feature family is universally best. Composition is cheap but coarse; alignment and structure add biological context; learned embeddings may capture richer patterns but require model inference and careful versioning.

DNA / RNA · SEQUENCE

Composition

GC%, AT/GC ratio, nucleotide frequency, sequence length, ambiguity rate

O(n)single scan

DNA / RNA / PROTEIN

k-mer / n-gram

Counts or normalized frequencies of substrings of length k.

O(n + |Σ|^k)time plus dense output

PROTEIN · SEQUENCE

Composition & physicochemical

AAC, dipeptide, molecular weight, charge, hydrophobicity, entropy

O(n)after lookup tables

SEQUENCE · REFERENCE

Alignment-derived

identity, coverage, score, conserved position, profile/PSSM-like evidence

O(mn)exact pairwise DP; searches often heuristic

RNA · STRUCTURE

Secondary structure

MFE, paired fraction, stem/loop counts, ensemble-derived measures

O(n³) time · O(n²) memoryclassical DP baseline

PROTEIN / NUCLEIC ACID

Language-model embedding

per-token or pooled representation from a versioned pretrained model

Attention ≈ O(n²)standard self-attention; architecture-dependent

GENOME · ANNOTATION

Genomic context

gene distance, exon/intron overlap, conservation, regulatory annotation

O(log R + h)typical indexed interval query; implementation-dependent

MOLECULE · NETWORK

Graph and interaction

degree, centrality, neighborhood aggregation, interaction embeddings

O(V + E) → higherdepends on graph algorithm and layers

● Usually cheap per sequence● Context or reference dependent● Compute/memory intensive

02 · SEE THE CALCULATION

A feature vector is the output of several different algorithms—not one extraction step.

The illustration uses one RNA sequence. Cheap scans share the same input, while alignment, folding and embedding invoke separate engines and reference versions.

RNA_001 · n = 300AUGGCUAUGC…GGAUACsha256: 91b…e42

→

SCANGC% · length · k-mer≈ O(n)

ALIGNreference similarityDP worst case O(mn)

FOLDMFE · paired fractionclassical O(n³)

EMBEDmodel vectorattention ≈ O(n²)

→

FEATURE VECTOR v3

[0.57, 300,
 0.021, …,
 -84.2, 0.61,
 e₁ … e₇₆₈]

nO(n)300 → 600 ≈ 2× work

n²O(n²)300 → 600 ≈ 4× work

n³O(n³)300 → 600 ≈ 8× work

03 · COMPLEXITY IS NOT WALL-CLOCK TIME

Big-O explains growth; benchmarking explains waiting.

Runtime also depends on implementation, hardware, batching, I/O, reference database size, model size and sequence-length distribution. The table separates asymptotic shape from a measurement plan.

FeatureInput variablesTimeMemory / OutputBenchmark evidence

GC / AACn = sequence lengthO(n)O(1) or fixed vectorsequences/s per CPU core

k-mer countn, k, alphabet |Σ|O(n)Sparse O(min(n,|Σ|ᵏ)); dense O(|Σ|ᵏ)k · sparsity · serialization

Pairwise alignmentm, nO(mn)Classic matrix O(mn); optimized variants differcell updates/s · traceback

Database searchquery + databaseheuristic / data-dependentindex + hitsDB version · size · sensitivity parameters

RNA foldingnO(n³)O(n²)length bins · mode · constraints

Transformer embeddingn, hidden d, layers Lattention O(Ln²d), broadlyattention activations grow quadraticallyGPU · batch · precision · pooling

04 · INTERACTIVE COST SCENARIO

How many times will the lab pay for the same deterministic feature?

This is an illustrative capacity model—not a hardware benchmark. Replace the baseline seconds with measurements from your own tool, sequence-length bin and machine.

SequencesMedian lengthExperiments / modelsWorkersBaseline seconds/sequence at n=300Growth class

One complete build—parallel idealized time

Without feature store——

Compute once + reuse—feature read cost excluded / usually much smaller

Avoidable recomputation——

Read the estimate correctly

The calculator assumes every experiment recomputes every sequence, workers scale perfectly and there is no queue, I/O or failure. Real systems scale less cleanly. Its purpose is to expose multiplication: sequence count × per-sequence cost × experiment count.

05 · WITHOUT A FEATURE STORE

The notebook becomes an invisible compute scheduler.

Each student or model rebuilds features with slightly different tools and parameters. Waiting grows, results diverge and no one can tell whether two columns are truly comparable.

100,000 sequencessame immutable input

Model A → fold + align + embed

Model B → fold + align + embed

Model C → fold + align + embed

Student 01…40 → repeat again

N × Ecompute jobsplus inconsistent versions and failed reruns

Repeated CPU/GPU hours

Deterministic folding or embeddings are regenerated for every experiment.

Reference drift

BLAST/database-derived features silently change after a database update.

Tool drift

Library, model weights or folding parameters differ across notebooks.

Queue amplification

Forty students submit identical GPU jobs instead of sharing one approved build.

No resumability

A failed 80% run may restart because intermediate features were not persisted.

Untraceable evidence

A model artifact survives, but the exact feature-generating environment does not.

06 · BIOINFORMATICS FEATURE STORE ARCHITECTURE

Cache the evidence—but preserve how it was produced.

Sequence identity alone is not a valid key. A feature also depends on algorithm, parameters, tool/container, model weights and reference database version.

SEQUENCE REGISTRYsequence_id · checksum · alphabet · length

→

FEATURE JOBdefinition + parameters + environment

→

OFFLINE FEATURE STOREParquet/table · partition · vector index

REFERENCE REGISTRYdatabase/model/tool versions

↗

METADATA & LINEAGEowner · created_at · code commit · quality

→

CONSUMERStraining · analysis · API · classroom

Figure 1. Store values and provenance together. Consumers request an immutable feature version rather than rerunning a hidden notebook cell.

FEATURE CACHE KEY

SHA256(sequence) + feature_name + feature_version + parameters_hash
+ tool_container_digest + reference_database_version + model_weights_digest

07 · LAB: DEFINE AND STORE CHEAP FEATURES

Start with transparent sequence features, then preserve their contract.

This Python example emits fixed-schema DNA/RNA composition and sparse k-mer counts. It is intentionally small enough to inspect before using a workflow engine.

from collections import Counter
from hashlib import sha256

def sequence_features(sequence: str, k: int = 3) -> dict:
    seq = sequence.upper().replace("U", "T")
    counts = Counter(seq)
    valid = sum(counts[b] for b in "ACGT")
    kmers = Counter(seq[i:i+k] for i in range(len(seq)-k+1)
                    if set(seq[i:i+k]) <= set("ACGT"))
    return {
        "sequence_sha256": sha256(seq.encode()).hexdigest(),
        "length": len(seq),
        "gc_fraction": (counts["G"] + counts["C"]) / valid if valid else None,
        "ambiguous_fraction": 1 - valid / len(seq) if seq else None,
        "k": k,
        "kmer_counts": dict(kmers),
        "feature_version": "sequence_basic_v1"
    }

Test the contractEmpty sequence, all-N sequence, lowercase, RNA U, invalid symbols, k > n, repeated input and checksum stability.

08 · MATERIALIZATION POLICY

Store what is costly, reused and reproducible—not every experimental column forever.

The store has its own storage and governance cost. Decide by compute-to-read ratio, reuse count, determinism, size, privacy and invalidation frequency.

FeatureStore?ReasonInvalidate when

GC%, AAC, lengthUsually yes, compactCheap but extremely reusable; fixed schema.definition changes

k-mer sparse vectorOftenReuse can justify size; partition by k/alphabet.k, normalization, filtering

Alignment / profileStrong candidateReference search is expensive and version-sensitive.DB/tool/parameters change

RNA structureStrong candidateCubic baseline makes reuse valuable.energy model/constraints/tool

EmbeddingYes when reusedGPU inference and model loading are costly; vectors can be large.weights/tokenizer/pooling

One-off exploratory transformMaybe notLow reuse may not repay storage and governance.recompute if needed

09 · STUDENT CHALLENGES

Turn computational biology into a measurable data-engineering decision.

Benchmark GC, 3-mer and 6-mer features across length bins; separate CPU from serialization time.

Measure RNA folding at four lengths and test whether observed growth resembles n³ on your machine.

Design a feature key for a BLAST-derived feature, including database and parameter versions.

Calculate CPU/GPU-hours for 50 experiments with and without reuse; include queue and failure assumptions.

Create a parity test showing a stored embedding equals a freshly computed embedding within a stated tolerance.

Write a retirement policy for unused 768-dimensional embeddings while preserving model reproducibility.

TECHNICAL REFERENCESNCBI · Biological Sequence Analysis ViennaRNA · RNAfold LinearFold · classical cubic baseline comparison Computational complexity of self-attention

THE CENTRAL IDEA

A feature store does not make biology simpler. It prevents the same computational evidence from being paid for—and interpreted differently—again and again.

Hash the sequence
Version every dependency
Measure before estimating
Materialize expensive evidence
Test parity and provenance
Retire unused features