Hedera :: genomic seed design tool

Hedera Homepage

Hedera is a program to select and design spaced seeds and transition-constrained spaced seeds. This tool is not maintained anymore, because a more general framework for subset seeds is currently developed and available in the iedera program. However Hedera is still available, because it is much less complicated to use...

Main features of Hedera are:

• ability to set the alignment probability distribution (4 parametrized models are proposed, they are automata equivalent to the ones proposed in Optimal spaced seeds for Hidden Markov models by B. Brejova, T. Vinar and D. Brown.)
• ability to set the alignment model length/homogeneity
• ability to generate spaced seeds or transition constrained spaced seeds according to different parameters : seed weight, seed span, number of transition constrained elements inside a seed
• ability to enumerate all the seeds (very slow in practice) or randomize seed design before selection step
• ability to check given spaced / transition constrained seeds by command line
• ability to select either the best seed(s) or seed(s) over a given threshold, according to their sensitivity

If you need fast-growing seeds then use Hedera :-)

If you use this program in your work, please cite :

[1]    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.

Your are welcome!

Download

• Binaries: v1.05, g++ compiled
  [linux-i686, win32-i686, mac-os-x, dir]
• Source Code : v1.05
  [tar.gz, zip]
• Paper: A unifying framework for seed sensitivity and its application to Subset Seeds
  [html]
• Paper related: scripts and experiments + ERRATUM
  [dir]

Command line parameters

hedera [options]

• -h display this Help screen
• -v display Version

1. Probability model:
   -P <double>,<double>,... :
   
   • <double> x 3 : Bernoulli model
     (tv,tr,mt) (default : 0.15 0.15 0.7)

     set the probability to observe a transversion (tv), a transition (tr) or a match (mt). This is the default model used and the default value is -P 0.15,0.15,0.7 . It can be changed by -P 0.16,0.2,0.64 for example (the sum must be 1.0).

   • <double> x 9 : M3 Model
     (tv,tr,mt) x 3

     set the probability to observe a transversion (tv), a transition (tr) or a match (mt) on each codon position (equivalent to 3 Bernoulli models).

   • <double> x 27 : M14 Model
     (Pr(w) with w in {tv,tr,mt}^3)

     set the probability of each "tri-nucleotide" alignment word ({tv,tr,mt}^3) on each codon position. The main advantage of this model compared with the M3 model is that probabilities of codons are prefix-dependent.

   • <double> x (4x4 + 4x27) : HMM Model
     (4 x M14)

     this corresponds to four M14 models combined with four hidden states (and a 4x4 probability matrix) to switch from one M14 to another M14 model on each codon start.

2. Alignments:
   • -L <int> : fix the alignment length (default = 32)
   • -H <int> : restrict computation to homogeneous alignments of given score (default : disabled)
   • -U <int>,<int>,<int> : homogeneous alignments Unit scoring system (tv,tr,mt)
3. Seed model:
   Consider, either all (default) or randomized seeds with :
   • -F <int> seed family size (default 1)
   • -W <int> seed weight (default 9)
   • -T <int> seed nb of @ (default 0)
   • -A allows equivalence between pairs of @ and # in seeds
   • -S <int>,<int> seed span (default min=9,max=15)
   • -R <int> generate R randomized seeds/seed families
   Or consider only a given family :
   • -M <motif>^+ (example -M #-@#,##-#)
4. Output:
   • -o <str> Output file
   • -m <int>,<int> also compute M-matches sensitivity for the given range
   • -t <double>
     • 1.0 : display best seed(s) only
     • x.x : display seed(s) with sensitivity > x.x

Example

	    
* find 1 seed of weight 9 and span from 9 to 12, exhaustive search :

118 % hedera -W 9 -S 9,12
# Match Prob    Seed(s)
0.412746        ###-#-##-###


* find 2 complementary seeds of weight 9 and span from 9 to 12,  exhaustive search : slow ... :

117 % hedera -W 9 -S 9,12 -F 2
# Match Prob    Seed(s)
0.53041 ##-#--######,###-###-#-##


* find 2 complementary seeds of weight 9 and span from 9 to 16,  10000 random tests :

116 % hedera -W 9 -S 9,16 -F 2 -R 10000
# Match Prob    Seed(s)
0.540088        ####--#--#-###,##-###-####


* find ... of weight 9 and span from 9 to 16 that allows 2 transitions, 10000 random tests :

115 % hedera -W 9 -S 9,16 -F 2 -R 10000 -T 2
# Match Prob    Seed(s)
0.546137        ###-@##@#-##,##-#@--#---#@###


* find ...  allows 2@ to be replaced by 1#, 10000 random tests :

114 % hedera -W 9 -S 9,16 -F 2 -R 10000 -T 2 -A
# Match Prob    Seed(s)
0.547462        ###-@#--@--#-###,##-###@-#@##