Page SeedDesign

This page contains an essay on the state of the art of seed design. The goal of this essay is to give an unifying view on seed design. Most relevant papers on seed design are summarized here.

Optimal Threshold Computation for Non-Gapped Seeds

Ukkonen paper. q-Gram lemma.

Optimal Threshold Computation for Seeds

Burkhardt and Kaerkkaeinen paper. FPT algorithm. Bounding criterion.

Optimal Threshold Computation for Families of Seeds

Kucherov, Noe and Rotyberg paper. FPT algorithms. Expansion and Contraction. Periodicity.

Filter Analysis for Families of Seeds

Fontaine, Burkhardt and Kaerkkaeinen paper. BDDs.

Hit Probability Computation for Seeds

Keich, Li, Ma and Tromp paper. KLMT algorithm.

Hit Probability Computation for Families of Seeds

Li, Ma and Tromp paper. PatternHunterII.

Overlap Complexity Computation for Families of Seeds

Ilie and Ilie paper.

Hardness Results

Nicolas and Rivals paper. Keich, Li, Ma and Tromp paper. Kaerkkaeinen paper.

Comments