A Statistical Model for Prokaryotic Promoter Prediction
Joseph Oppon

ekow@sanbi.ac.za

Winston Hidewinhide@sanbi.ac.za

South African National Bioinformatics Institute, University of the Western Cape
Bellville 7535, South Africa

1 Introduction
A simple, fast and sensitive model for identifying and predicting sequences which have non-random
statistical properties and therefore biologically active, such as promoters has been developed. This
statistical model, Penalized Triplet Frequency Distribution (PTFD) utilizes the information content ofpromoters (in triplets) and those of other set of sequences of di erent category e.g. coding sequences(also in triplets) to generate a hash table of scores for each of the 64 possible triplets. The hash table
is unique for each set of promoter and non- promoter sequences but generally similar in composition.
Cumulative score and therefore the performance of each sequence is assessed by (a) opening a 3bp
window and moving along the sequence one bp at a time to extract all the triplets ; (b) obtaining
each triplet's corresponding hash table value and (c) summing up all the hash table values of thetriplets found in the sequence. A cut-o value obtained by implementing the model on test promoter
sequences is used to predict promoters from non promoters. Our prediction results using Penalized
Triplet Frequency Distribution (PTFD) method are consistently around 93% True Positives (TP)and 10-14% False Positives (FP). These results are comparable to the kind of results obtained with
Neural Network and Hidden Markov Model predictions of promoters from non-promoters (results notshown). Our method is in addition, able to identify promoters sandwiched between other sequences
whether these are coding sequences, or non coding sequences between coding sequences with no known
promoter activity.

2 Method
Fifteen (15) pairs of promoter and non-promoter sequences were analyzed for their triplet frequency
distribution. Each set in the pair consisted of 40 sequences and each sequence length was 50bp long.
E. coli promoter sequences were selected 50bp upstream of their respective Transcription Start Point[1] 1993). Coding sequences used as non- promoter data were obtained from the current Genbank
release. To obtain the triplet frequency distribution of each set of sequence, all the sequences in theset (40) were concatenated. Actual triplet frequency distribution in each set was calculated by using
the formula:(No of triplets found inset)(43 )Frequency of each triplet =Total number of Nucleotides in Set
A system of rewarding triplets more common in promoter sequences and penalizing triplets prevalent in
non- promoters was implemented by subtracting each triplet's frequency in the promoter set from thatof the corresponding frequency in the non-promoter set. Fifteen separate hash tables were created forall fteen promoter/non promoter pair. An average hash table was also generated from all the fteen
hash tables (Table 1). Two types of tests were conducted with the newly created hash tables. First,
1000 coding sequences were tested with each hash table after a threshold gure has been obtained by
testing them on another set of promoter sequences (86) not used in the hash table generation Each set's
threshold was selected to obtain the desired percentage of true positive (TP) and used to determine
271

AAA
ACA
AGA
ATA
CAA
CCA
CGA
CTA
GAA
GCA
GGAGTA
TAA
TCA
TGA
TTA

=
===============0.77828
0.21749-0.03838
0.79747-0.02345-0.33263-0.452040.30705-0.15352-0.25800-0.14499
0.313440.79960
0.21536-0.10448
0.67593

AAC
ACC
AGC
ATC
CAC
CCC
CGC
CTC
GAC
GCC
GGC
GTC
TAC
TCC
TGC
TTC

=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=

-0.18764-0.51175-0.272930.17058-0.02345-0.17058-0.81666-0.00640-0.33903-0.66740-1.15782- 0.10661
0.04904
0.10875-0.27506
0.49895

AAG
ACG
AGG
ATG
CAG
CCG
CGG
CTG
GAG
GCG
GGG
GTG
TAG
TCG
TGG
TTG

================-0.18124-0.60343-0.04051
0.02985-0.39021-0.73776-0.84225-0.85930-0.09382-1.12370-0.36888-0.26866
0.49895-0.07676-0.75909
0.72924

AAT
ACT
AGT
ATT
CAT
CCT
CGT
CTT
GAT
GCT
GGT
GTT
TAT
TCT
TGT
TTT

================1.08746
0.377410.232420.96805
0.28359-0.03412-0.44564
0.66527-0.13007-0.48189-0.30278-0.30918
0.705780.27506
0.79960
1.88919

Table 1: Triplets and their corresponding hash values generated by subtracting the actual frequencyof the triplet in coding sequences from those of actual promoter sequences.
Sets
1
2
3
4
5
6
7
8

Cut-off--2.33640
0.992200.32000
0.22400-1.95200
1.31220
1.95200
2.72010

TP
(/86)
80
""
"
"
"
"
"

%
93.0
""
"
"
"
""

FP
(/1000)105130125141168
150
141
128%
10.5
13.0
12.5
14.1
16.8
15.0
14.1
12.8

Set
9
10
1112
13
14
15Av.

Cut-off--1.92010
1.98400-0.54330
0.25670
1.02420-0.80000-0.73580
1.09819

FP(/1000)
126
115
199
149
131
168
139
146%
12.6
11.5
19.9
14.9
13.1
16.8
13.9
14.6

Figure 1: Results from the fteen hash tables used to test the same set of promoter and non-promoter
sequences. Each threshold value was selected to obtain the speci ed percentage (93%) of true positives(TP). Also included is the results obtained on the average hash table.
the prediction from the coding sequences Fig. 1.The second test was done by selecting forty nine(49) sequences ranging from 120-900bp which contained promoter sequences. These sequences herebyreferred to as inter-orfs were obtained by selecting regions in E. coli genome between TAG/TGA/TAA
and ATG A 75bp window was opened and performance scores were obtained for each window. For
each inter-orf sequence, the best predicted score for the 75bp window was retained together with its
score. Thirty-eight (37) of the 49 predictions had either all of the promoter sequences or part of it(Fig. 2).

References[1] Lisser, L. and Margalit, H., Compilation of E. coli mRNA promoter sequences, Nucleic Acid Res.,
21(7):1507{1516, 1993.

272

PREDICTED SEQUENCETTTTCAATACTTCAATGACCGGTTATCAAGAAATCCTCACTGATCCTTCCTATTCTCGTCAAATCGTTACTCTTA
TGTATTGAGGTTATTAGCGAATAGACAAATCGGTTGCCGTTTGTTGTTTAAAAATTGTTAACAATTTTGTAAAATAAATAAAAATACGGCTTGAAACGAGCCAAATAGGGTTCTCGTAGGGGGAATAAGATGAATATTTTAGGTTTTTTTATTATCAATTTTAAAAAACTAACAGTTGTCAGCCTGTCCCGCTTATAAGATCATACGCCGTTATACGTTGTTTACGTAACAAAGAAATGCAGGAAATCTTTAAAAACTGCCCCTGACACTAAGAGAGTTTTTAAAGGTTCCTTCGCGAGCAAACAGGTTCGGAAAACGTTTGCGTTTTTTTTGCCGCAGGTCAATTCCCTTTTGGTCCGAACTCGCACATAATACAAATATTGATAGCCTGAATCAGTATTGATCTGCTGGCAAGAACAGACTACTGTATATAAAAACAGTATAACTTCATGTTAATTATCCTAAAGGGGTATCTTAGGAATTTACTTTATTTTTCATCCCCATCACTCTTGATCGTTATCAATTGGGAGAAATCGCAACTGTTAATTTTTTATTTCCACGGGTAGAATGCTCGCCGTTTACCTGTTTCGCGCCACTTCCTTTTGTCTCACCTTTTAATTTGCTACCCTATCCATACGCACAATAAGGCTATTGTACGTATGCAAATTAATAATATTTTTTTATTTAATCGATAACCAGAAGCAATAAAAAATCAAATCGGATTTCACTATATAATCTCACTTTATCTAA
TCGATATCATGGGCCTTAGTCGCCGAATGTACTAGAGAACTAGTGCATTAGCTTATTTTTTTGTTATCATGCTAACATATTAAAAATCAGAAAAACTGTAGTTTAGCCGATTTAGCCCCTGTACGTCCCGCTTTGCGTGTATTTCATAAC
AAATTTCTGCTAATCGAAAGTTAAATTACGGATCTTCATCACATAAAATAATTTTTTCGATATCTAAAATAAATCCGTTGATATTTTCGCCTAACGTCAGAGGTAGCACCGTAATCCGCGTCTTTTCCCCGCTTTGTTGCGCTCAAGACGCTAAATAAGTCGCGGGCATAAGGCATATTTTCATCAACAAGGATTTTCACGTTTGTGTTACCTGTATGAGACGAG
TTTGTATATCTTGGTTGAGTTTATTGGCAACCCTATCACTGCCATGTTTATCGCCGTGTTTGTCGCCTATTATGTGTACTGTACTAAAGTCACTTAAGGAAACAAACATGAAACACATACCGTTTTTCTTCGCATTCTTTTTTACCTTCCAAAAATGTTATCCACATCACAATTTCGTTTTGCAAATTGGGAATGTTTGCAATTATTTGCCACAGGTAACAAAAATGTTTCTCTAACGACTTCCCTTTTAGCCTTAAAGATAAAATCCATTTTAATTTCAGTCATTTAATAAAGAATTTTAAAAGTTAACCCTTCGACCCACTTCACTCGCGCTTGCATTTTTGCTACTCCACTGCGTCAATTTTCCTGACAGAGGTAGTATTTTGCTTTTTTCAGAAAATAATCAAAAAAAGTTAGCGTGGTGAATCGATACTTTACCGGTTGAATTTG
CCTTATAACCATTAATTACGAAGCGCAAAAAAAATAATATTTCCTCATTTTCCACAGTGAAGTGATTAACTATGC
TTATTCCTCAACCCTTTTTTTAAACATTAAAATTCTTACGTAATTTATAATCTTTAAAAAAAGCATTTAATATTGGAAACGTTTCGCTGATGGAGAAAAAAATGAAAAAAGGCACCGTTCTTAATTCTGATATTTCATCGGTGATCTCCCGAGTAAACCTCTCCTTAGTAAACTCTGAAAAAGTAATAACACAACGTTACGACCCGATATTTTCTAAGTCTAATGTGTTGACTTCGTATTAAACATACCTTATTAAGTTTGAATCTTGTAATTTCCAACGCTTCCCGTTTTATCTTAAATTTTCTTTACGGTCAATCAGCAAGGTGTTAAATTGATCACGTTTTAGACCATTTTTTCGTCGTGAAACTAAAAAAATTTCTCGCGACCGGGTTTTTTATTTGTCACGATTTTGCGTTACCCTTGCATCTCTTTGAGGTACAGGGAAAAAAAAATGCATATAATTTTAACGGCTATTTGGGATTTGCTCAATCTATACGCAAAGAAGTTTAGATGTCCAGATGTATTGTTTCTGTGAGCAATTATCAGTCAGAATGCTTGATAGGGATAATCGTTCATTGCTATTCTACCTATCGCCATGAATGTTTCTTCATCGTGTCGCATAAAATGTGACCAATAAAACAAATTATGCAATTTTTTAGTTGCATGAACTCGCATATCATTTGATGCCCTTTTTGCACGCTTTCGTACCAGAACCTGGCTCATCAGTGATTTTCTTTGTCATAATCATTGAATAAATTTTATTCATATTGTTATCAACAAGTTATCAAGTATTTTTAATTAAAATGGAAATTGTTTTTGATTTTG
ATTTTGGATAACCCTTCCAGAATTCGATAAATCTCTGGTTTATTGTGCAGTTTATGGTTCCAAAATCGCCTTTTG
AAAACTCTGCTTTTCAGGTAATTTATTCCCATAAACTCAGATTTACTGCTGCTTCACGCAGGATCTGAGTTTATG
AAATTGCGATGAAATGTGAGGTGAATCAGGGTTTTCACCCGATTTTGTGCTGATCAGAATTTTTTTTCTTTTTCCCTTTTGTAAAGACGAACAATAAATTTTTACCTTTTGCAGAAACTTTAGTTCGGAACTTCAGGCTATAAAACGAATCTTATTGAATATGATTGCTATTTGCATTTAAAATCGAGACCTGGTTTTTCTACTGAAATGATTATGACTTCAATGCCTCCAGTGCGGTGTTTAAATCTTTGTGGGATCAGGGCATTATCTTACGTGATCAGAATAAACAACCCTCTTTAAGTTACAGGAAAAGCCAAAGCTGAATCGATTTTATGATTTGGTTCAATTCTTCCTTTAGCGGCATAATGTTTAATG
CCATAATGTTATACATATCACTCTAAAATGTTTTTTCAATGTTACCTAAAGCGCGATTCTTTGCTAATATGTTCGTGTCAATGATTGTTGACAGAAACCTTCCTGCTATCCAAATAGTGTCATATCATCATATTAATTGTTCTTTTTTCA
GCATTTTTACACACTGTGATGAAAAAATCTCCCGTCATTTATAATGATAAGTGTTTTTACCACTTCCCCTTTTCGCAAAAAGGTTGTGTAAAGCAGTCTCGCAAACGTTTGCTTTCCCTGTTAGAATTGCGCCGAATTTTATTTTTCTAC
CTTTTATTCAAACTTTCAAATTAAAATATTTATCTTTCATTTTGCGATCAAAATAACACTTTTAAATCTTTCAATTTTTAATAAATGCTCACGTTCTACGGTAAATTTCATAGGTTTACGATGACAATGTTCTGATTAAATTTGAAAAATGTAGGGATTGCTCATCAGATGTCCAGATCTTGATGAATTCCTATTTGTGAGCTACGTCTGGACAGTAACTTGTTA
GATTTTTGCAAGCAACATCACGAAATTCCTTACATGACCTCGGTTTAGTTCACAGAAGCCGTGTTCTCATCCTCC

BEST SC.
18.00706
34.80297
25.21843
20.41013
15.92599
18.30775
14.05808
32.28686
15.00058
28.19079
38.71991
19.58493
20.09882
37.61114
6.83401
15.91532
18.45270
25.98812
30.19303
41.06753
11.32669
30.71754
25.54891
47.73726
12.10496
18.29702
31.26764
26.87733
21.54236
22.32491
13.70628
26.96261
20.24805
51.44744
24.26313
17.76397
30.92437
29.40191
27.65771
13.4482622.10529
31.86892
29.80917
32.02034
23.60644
49.43671
30.17592
11.42687
12.91093

NAME
lpd
glnS
suc AB
pyrd
umu
narG
pyrF
sodB
aroH
katE
manX
flaA
div
phe
nupGmalT
rbs
rho
cya
cdh
metBL
oxyR
tufB
secE
aceB
exA
melA
groE
htrA
tonB
hisB
ptsH
glpD
tyrR
purR
purMN
btuB

Figure 2: The best predicted sequences (75bp) from each of the 49 inter-orfs using penalized triplet
frequency distribution together with their corresponding scores. Underlined are nucleotide sequences
found in original promoter sequence (Lisser and Margalit, 1993). Also the rightmost column shows
the names of the promoters, which were partially or fully predicted.

273