Iedera :: subset seed design tool

home > DNA > yass

Table of contents

Iedera overview

Iedera is a program to select and design subset seed and vectorized subset seed patterns. Spaced seeds (see the quick introduction) and transition constrained spaced seeds can be perfectly represented in the subset seed model. Moreover, BLASTP-like seeds, and more generally Vector seeds (seeds with cumulative score constraint) can also be represented by vectorized subset seeds (which is a subset seed with an additional score constraint).

Iedera is applied to both lossy and lossless seed design. It is already used to design spaced seeds templates for read mappers (see below), to design subset seed templates for protein sequences (see below) or nucleic sequences (see below). Recent applications also include sub profile-HMM read mapping problem (see below), alignment-free distances and SVM string kernels with a new coverage criterion (see below), parameter-free spaced seed design (see below), and more recently minimally-overlapping words (see below) which are a better sampling alternative to minimizers.

This tool is experimental and is provided for research purposes only !! It natively supports two probabilistic models to describe the alignment sequence distribution (Bernoulli and Markov) and other models (as HMM) can be represented by probabilistic automata (see below).

The first version of Iedera was developed by L. Noe, G. Kucherov, and M. A. Roytberg. Since ~ 2010, Iedera is developed and maintained by L. Noe of the Bonsai team.

Main features of Iedera are: fast growing seeds

If you use this program in your work, please cite one of these papers:

[1]    G. Kucherov, L. Noe, M. Roytberg, Subset seed automaton, Proceedings of the 12th International Conference on Implementation and Application of Automata (CIAA 2007), LNCS 4783:180-191 , 2007.

[2]    G. Kucherov, L. Noe, M. Roytberg, A unifying framework for seed sensitivity and its application to subset seeds, Journal of Bioinformatics and Computational Biology, 4(2):553-569, 2006.

If you still need it, the old precursor named hedera is still there.

Your are welcome! We always appreciate to share new ideas and problems...

top^

Download

top^

Applications

Subset seeds for Applied Biosystems SOLiD® read mapping

The method has been extended and applied to design seeds on HTS reads, taking into account both the DNA variability and also reading errors [3,4]. We have an additional webpage that describes the technical details to design seeds for the SOLiD® scheme + a read mapping tool.

[3]    L. Noe, M. Girdea, G. Kucherov, Seed design framework for mapping SOLiD reads, Proceedings of the 14th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2010), LNCS 6044:384-396, 2010.

[4]    L. Noe, M. Girdea, G. Kucherov, Designing Efficient Spaced Seeds for SOLiD Read Mapping, Advances in Bioinformatics, Article ID 708501, 2010.

top^

Subset seeds for protein alignment

Subset-seeds have been used to detect protein homologies. Details of the models used, together with experiments to design seeds and measure their sensitivity on real datasets are given in the paper On subset seeds for protein alignment [5] and Subset Seed Extension to Protein BLAST [6]. We have an additional webpage that describes the technical details to design seeds for proteins.

Moreover, a new software named plastp has been developped by Van Hoa Nguyen and Dominique Lavenier of the INRIA Symbiose team. It is similar in use to blastp (by now, it provides plastp, tplastn, plastx and tplastx) but is highly parallel (both efficient SIMD and Multithreading) and uses subset seed patterns: I thus give this script to transform seeds alphabets and seed patterns obtained with iedera into readable seeds for plastp.

[5]    M. Roytberg, A. Gambin, L. Noe, S. Lasota, E. Furletova, E. Szczurek, G. Kucherov, On Subset Seeds for Protein Alignment, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(3):483-494, 2009.

[6]    A. Gambin, S. Lasota, M. Startek, M. Sykulski, L. Noe, G. Kucherov, Subset Seed Extension to Protein BLAST, International Conference on Bioinformatics Models, Methods and Algorithms (Bioinformatics), 149-158, 2011.

top^

Spaced seed design on profile HMMs for precise HTS read-mapping

[ongoing] (iedera v1.06 α ≥ 5) Spaced seeds have been also designed to comply with the restricted alignment length that a read produces, when aligned against a profile-HMM, itself combined with the variable conservation level along the profile-HMM : seeds can thus be designed / position-designed on the full profile-HMM, by taking into consideration this conservation level along all the possible read alignments (windows) on this profile-HMM. We have a draft paper and an additional webpage that describes the experimental details.

top^

Transition seeds and new human/mouse alignments

How better transition seeds may help finding new significant alignments when the transition/transversion rate is high? Last software (with Iedera seed design) may help [7] :

[7]    M. C. Frith, L. Noe Improved search heuristics find 20 000 new alignments between human and mouse genomes, Nucleic Acids Research, 42(7):e59. 2014

top^

Spaced seed coverage and SVM string-kernels and k-mer distances applications

(iedera v1.06 α ≥ 7) Spaced seeds have been used recently in alignment-free distances and SVM string-kernels. We have adapted a new coverage criterion (defined as the number of matches covered by at least one maching symbol from one seed hit) to comply with these new problems. Details of the models used, together with experiments to measure seeds are given in the paper A Coverage Criterion for Spaced Seeds and Its Applications to Support Vector Machine String Kernels and k-Mer Distances [8]. We have an additional webpage that describes the technical details.

[8]    L. Noe, D. E.K. Martin A Coverage Criterion for Spaced Seeds and Its Applications to Support Vector Machine String Kernels and k-Mer Distances, Journal of Computational Biology, 21(12). 2014

top^

Spaced seed dominance and applications to hit integration, dirac or heaviside models / lossless seeds

(iedera v1.06 α ≥ 9) Spaced seeds have been selected by Mak & Benson 2009 with a new spaced seed dominance criterion on the Bernoulli model; we extend their work on the Hit integration model, and propose two discrete Dirac and Heaviside models that can carry lossless seeds in the same framework. You will find the whole description in the paper Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds [9], you can also get the full experimental results on this additional webpage that provides the scripts, some technical details, and many plots (pdf or html) where you can pick good seed patterns according to your needs.

[9]    L. Noe, Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds, Algorithms for Molecular Biology, 12(1). 2017

top^

Minimally-overlapping (spaced-like) words for sequence similarity search

(iedera 1.07 hfkn_check / iupac branch) Minimally-overlapping words have been shown to be better - more sensitive - than minimizers for selecting conserved k-mers, in Frith & all 2020. We try to further optimize the main result at the end of the paper with a spaced-like pattern, and with a quite good success.

[10]    M.C. Frith, L. Noe, G. Kucherov, Minimally-overlapping words for sequence similarity search, Bioinformatics. 2020

top^

Usage

Quick introduction

If you simply need to design spaced seed templates (with the commonly used default parameters), try this first:

(1) to design one spaced seed pattern of weight 9, span (seed length) from 9 to 15, type: 

    ./iedera -spaced -w 9,9 -s 9,15 (or ./iedera.exe -spaced ... )

    you will obtain the following result, where the seed pattern is given by a set of '#' and '-':
    ##-##-#-#---###         0.999996       0.729156      0.270844
    first column gives      second         third is      last is distance
    the seed                gives          sensitivity   to (1,1) coordinate 
                            selec-                       in sel/sen.
                            tivity


(2) to design one spaced seed template of weight 11, span from 11 to 18, type:

    ./iedera -spaced -w 11,11 -s 11,18

(3) to design 2 complementary spaced seed patterns of weight 11, span from 11 to 20, randomly 
    drawn 10000 times with an additional hill-climbing heuristic, type:

    ./iedera -spaced -w 11,11 -s 11,20 -n 2 -r 10000 -k

(4) a good change can be to reset the default alignment length to 40 (on previous examples, it
    was set to 64), type:

    ./iedera -spaced -w 11,11 -s 11,18 -l 40

    and see the difference: smaller span of the seed been selected and also lower sensitivity on 
    shorter alignments compared with (2).

(5) to design "lossless" seeds (with up to 2 mismatches for an alignment of length of 25), type :
    
    ./iedera -spaced -L 1,0 -X 2 -l 25 -w 12,12 -s 18,20 -r 10000 -k

    and see the explanation below.
top^

More details:

To understand subset seeds, the first objects that need to be described are the alignment alphabet A and the seed alphabet B built upon A.

Let start with A: alignments can be represented by a succession of mismatches or matches (at first sight), thus with a simple binary definition for A : A = {'0','1'}. Each seed letter b of B is defined as a subset of the alignment alphabet A ; e.g. if A = {'0','1'} then there are four choices for b: b is either the empty set {}, either one of partial sets {'0'} or {'1'}, or the full set {'0','1'}.

A seed letter b "detects" a if the subset describing b contains a. E.g. if we consider that A = {'0','1'} is defined by '0' for mismatch, '1' for match, then the seed letter '-' defined by the subset {'0','1'} is commonly called jocker since it "detects" any letter of A. The seed letter '#' defined by the subset {'1'} is called a must match letter since it only "detects" the match symbol '1' of A. Note that the two other possible seed letters (empty set {} and "must mismatch" {'0'}) are by no way useful to detect interesting alignments.

A seed π defined as a word on B (π = b1b2...bs) "detects" the alignment defined as a word on A (a1a2...an) at a given position p (0 ≤ p ≤ n - s) iif for all i (1 ≤ i ≤ s)     bi contains ai+p.     E.g if we consider that A = {'0','1'}, B = {'-','#'} where '-' is defined by the subset {'0','1'} and '#' is defined by the subset {'1'}, then the seed π='##-#' detect the alignment '101101111' at the 3th and 6th positions (thus for p = 2 and p = 5): 

101101111
  |||||||
..##-#|||
.....##-#

Finally, for a given seed π to "detect" an alignment, we have to find at least one position p satisfying the previous condition. iedera does this checking in parallel on the full set of "interesting" alignments using automata theory (see paper [2] for more details).


Now, we can show into more technical details how to set the alignment alphabet, the seed alphabet, and their compatibity matrix in iedera: 

(1) Default alignment alphabet A and seed alphabet B are of size 3. Note that you can modify both 
    sizes using the -A and -B parameters. Alignment and seed alphabet letters are represented 
    (by default) with the symbols "0..9A..Za..z": thus, an alphabet of size 3 is composed of the 
    symbols '0','1','2'.

    As alignments and seeds have the same set of symbols by default, it is a good idea to 
    override B  symbols with the following parameter:

    -BSymbols '-@#'

(2) The subsets are given by a boolean matrix (subset matching matrix) of B lines and A columns. 
    The default boolean subset seed Matching matrix is defined as an upper triangular:

    {{1,1,1},
     {0,1,1},
     {0,0,1}}

    each seed letter is represented by one line inside this boolean matrix: 
    - seed letter '0' or '-' (1st line) is called joker since it accepts any letter of A: {1,1,1}
    - seed letter '1' or '@' (2nd line) accepts the 2nd & 3rd letter of A but not the 1st: {0,1,1}
    - seed letter '2' or '#' (3rd line) is usually a must match letter, since it only accepts the 
      last letter '2' of A which usually represents a match.

    You can modify this binary matrix using the -M option:

    ./iedera -A 3 -B 4 -M \{\{1,1,1\},\{0,1,1\},\{1,0,1\},\{0,0,1\}\} -BSymbols '-@x#'

    in this example, we have defined 4 seed letters on alignment alphabet of size 3: 

    '-'={'0','1','2'},  '@'={'1','2'}, 'x'={'0','2'} and  '#'={'2'}

Once the two alphabets are defined (and the subset matrix possibly set), we need to define probabilistic distributions for the alignment alphabet: two of them are needed to describe the foreground distribution (for true "target" alignments) and background distribution (random "bad" alignments). We choose here to use the simplest Bernoulli model. 

(3) Each alignment letter of A has a foreground and background probability to appear, 
    according to models (Bernoulli or Markov), look at the -f and -b commands.

(a) A commonly used parameter for spaced seeds is "-f 0.3,0.7 -b 0.75,0.25" that gives, for the 
    alignment alphabet A, a foreground probability of 0.7 for the match symbol (respectively of 
    0.3 for mismatch symbol), and a background probability of 0.25 for the match symbol
    (respectively of 0.75 for mismatch symbol).

(b) A classical example to design spaced seeds of weight 11, span 12 to 18, on Bernoulli
    alignments of length 64, using previous probabilities:

    ./iedera -A 2 -B 2 -l 64 -w 11,11 -s 11,18 -f .3,.7 -b .75,.25

    111010010100110111      1       0.467122        0.532878

    first column gives      second  third is        last is distance
    the seed                gives   sensitivity     to (1,1) coordinate 
                            selec-                  in sel/sen.
                            tivity

    It is possible to use the "-spaced" parameter that represents shortcut for 
    "-A 2 -B 2 -f .30,.70 -b 0.75,0.25 -BSymbols '-#' -l 64 -w 9,9 -s 9,15".
    You only have, when needed, to override weight and span (e.g. "-spaced -w 11,11 -s 11,19").

(c) Another example to design transition-constrained seeds of weight 11, span 12 to 18:

    ./iedera -A 3 -B 3 -l 64 -w 11,11 -s 12,18  -f .15,.15,.70  -b .50,.25,.25  -r 10000

    221022002120102122      1       0.476753        0.523247

    here we focus on probabilities:
    -f .15,.15,.70  gives the probability to have a transversion, a transition, or a match 
                    in a target ("good") foreground alignment,
    -b .50,.25,.25  does exactly the same, but for a random ("bad") background alignment.

    It is also possible to use the "-transitive" parameter that represents shortcut for
    "-A 3 -B 3 -f 0.15,0.15,7 -b 0.5,0.25,0.25 -BSymbols '-@#' -l 64 -w 9,9 -s 10,15 -i 0,2,8".
    You have, when needed to override weight, span, and signature that
    represents the number of symbols '(-)@#' allowed in a seed
    (e.g. "-transitive -w 11,11 -s 12,19 -i 0,2,10").

(d) A third example with 2 seeds of weight 12, span 12 to 19:

    ./iedera -A 3 -B 3 -l 64 -w 12,12 -s 12,19  -f .15,.15,.70  -b .50,.25,.25  -r 50000 -k -n 2
    2220211022120020122,2121022020012201222 1       0.500499        0.499501

    Here, we cannot use full enumeration of all the pair of seeds (would take decades), so we use 
    the "-r 50000 -k" parameter to randomly generate pair of seeds with a hill-climbing heuristic

Finally, it is possible to design seeds by taking into account the fact that they are lossless according to a given criterion: in this case, sensitivity (e.g "0.9790") is replaced by "[lossless]" when the seed is lossless. Note that a seed with sensitivity equal to 1.0 does not mean that it is lossless (although not far from being perfect ... there are still a few alignments that escape)


(4) About the design of lossless spaced seeds: 

(a) we want to find a seed of weight 12 that matches all alignments of length 25 with 
    at most 2 mismatches: we thus fix a penalty of 1 for a mismatch and 0 for a match 
    (-L 1,0) and set a max penalty of 2 (-X 2)

    ./iedera -spaced -s 12,19 -w 12,12 -l 25 -L 1,0 -X 2
    #-###--#-###--#-### 1       [lossless]      5.96046e-08


(b) if we want to find several (eg. 2) seeds, full enumeration is unusable, so we hope 
    to be lucky with these parameters after one full night ...
    ./iedera -spaced -l 25 -L 1,0 -X 2 -n 2 -s 20,21 -w 14,14  -r 100..some.zeros..00 -k
    ####-#-##--####-#-##,#-##--####-#-##--####  1       [lossless]      7.45058e-09
top^

Command line parameters

iedera [options]

   Seed Model:

    Data
    SubsetSeed/VectorizedSubsetSeed
    SubsetSeed/LosslessSubsetSeed

  Alignments:

  Seed Enumeration:

  Miscellaneous:

  Nucleic spaced seeds: (shortcuts that simulates hedera parameters)

top^

Probabilistic automaton file format

A small but detailled example:

First line gives the number of states (2 in the next example). Then each state is described (its current state number is given and a final flag is set). For each state, next lines describe a list of transitions that start from this state: for each letter of the alignment alphabet (here 0, 1 or 2), the number of transitions outgoing from the current state on the given letter is provided, followed on each new line by a single transition (more precisely, its destination state and its probability). Finally, note that the initial state is by convention always the state 1. 

2 → number of states
      0    1 → Current state : current state number + final state flag
           0    1 → alignment alphabet letter + number of transitions outgoing from current state on this letter
                0    0.04 → Current transition : destination state number + probability to follow this transition
           1    2
                0    0.06
                1    0.10
           2    1
                0    0.80
      1    0
           0    1
                1    0.05
           1    1
                1    0.25
           2    1
                0    0.70

The previous description is equivalent to this probabilistic automaton:

probabilistic automaton example