BIOINFORMATICS

Vol. 18 no. 2 2002
Pages 298–305

Extensive Feature Detection of N-Terminal
Protein Sorting Signals
Hideo Bannai 1, Yoshinori Tamada 2, Osamu Maruyama 3, Kenta
Nakai 1 and Satoru Miyano 1
1

Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1
Shirokanedai, Minato-ku, Tokyo, 108-8639, JPN, 2 Department of Mathematical
Sciences, Tokai University, 1117 Kitakaname, Hiratuka-shi, Kanagawa, 259-1292,
JPN and 3 Faculty of Mathematics, Kyushu University, Kyushu University 36, Fukuoka,
812-8581, JPN

ABSTRACT
Motivation: The prediction of localization sites of various
proteins is an important and challenging problem in thefield of molecular biology. TargetP, by Emanuelsson et al.
(2000) is a neural network based system which is currently
the best predictor in the literature for N-terminal sorting
signals. One drawback of neural networks, however, is that
it is generally difficult to understand and interpret how andwhy they make such predictions. In this paper, we aim togenerate simple and interpretable rules as predictors, andstill achieve a practical prediction accuracy. We adopt an
approach which consists of an extensive search for simple
rules and various attributes which is partially guided byhuman intuition.
Results: We have succeeded in finding rules whose
prediction accuracies come close to that of TargetP, whilestill retaining a very simple and interpretable form. We also
discuss and interpret the discovered rules.
Availability: An (experimental) web service using rules obtained by our method is provided at
http://hypothesiscreator.net/iPSORT/.
Contact: bannai@ims.u-tokyo.ac.jp

INTRODUCTION
Most proteins are first synthesized in the cytosol, andcarried to specified locations, such as mitochondria orchloroplasts. In most cases, the information determining
the subcellular localization site is represented as a shortamino acid sequence segment called a protein sorting
signal (Nakai, 2000). If we could somehow detect theamino acid sequence encoding this information, we would
be able to predict the localization sites.
Prediction of localization sites is useful in various
ways. Because cellular functions are often localized in
specific compartments, the prediction of localization sitesof unknown or unannoted proteins may be used togain some indication of its function. For example, theinformation may be used to screen candidate genes forc Oxford University Press 2002°

drug discovery. Further, if the rules for prediction were
biologically interpretable, this knowledge could help indesigning artificial proteins with desired properties.
TargetP (Emanuelsson et al., 2000), a neural network
based predictor, is known to be the best predictor in
the literature for N-terminal sorting signals. However,
although neural networks are “readily available” and“often successful in practice”, they are also infamous
for the difficulty involved in trying to understand andinterpret their meaning (Chou, 2001). PSORT (Nakai andKanehisa, 1992; Nakai and Horton, 1999) and MitoProt(Claros and Vincens, 1996), unlike TargetP, are systems
which incorporate existing knowledge about sorting
signals, but they use various real numbers as “weights”
in their prediction rules which also may not be triviallyinterpretable. Also, they are somewhat obsolete and theirperformance is unsatisfactory compared to TargetP.
The aim of this work is to derive simple and interpretable rules which can be used to predict subcellular
localization sites, while still achieving a practical prediction accuracy. Through our discovery oriented approachto the problem, we managed to find very simple andinterpretable rules with prediction accuracies which comefairly close to TargetP.
We will first review the existing knowledge about the Nterminal signals, and then describe the general idea of ourapproach.

N-Terminal Sorting Signals
The signals we consider are signals known to be on
the N-terminal of the protein. Mitochondrial targeting
peptides (mTP), chloroplast transit peptides (cTP), andsignal peptides (SP) are the typical N-terminal sorting
signals.
Mitochondrial targeting peptides are known to be richin arginine (R), alanine (A), and serine (S), while negatively charged amino acid residues (aspartic acid (D) andglutamic acid (E)) are rare (von Heijne et al., 1989). Only
298

Feature Detection of N-Terminal Sorting Signals

weak consensus sequences have been found. Further, they
are believed to form an amphiphilic α-helix important forimport into the mitochondrion.
Chloroplast transit peptides are known to be rare inacidic residues, and also believed to form an amphiphilic
α-helix (Bruce, 2000).
It has been established that a concrete consensus
sequence does not occur in signal peptides. Rather, athree-region structure is conserved: a positively charged
n-region, a hydrophobic h-region, and a polar c-region(von Heijne, 1990).

Overview of Our Approach
Several very important aspects in the process of scientificknowledge discovery are: 1) the generation or discoveryof good attributes, and ways of looking at the data, whichis then used to explain the data, 2) the incorporation ofand reflection on existing knowledge, and 3) the trial
and error interaction between the expert and the problem.
We have been developing a computer software libraryfocusing on these points to speed-up this process, andhave been applying it to various problems in the fieldof bioinformatics (Maruyama et al., 1998, 1999; Bannai
et al., 2001).
The overall idea of this approach is to create massive
amounts of very simple attributes and their trivial combinations, based on various known attributes. This way, if
such rules exist for the data, we can expect to overcome
the poor descriptive strength of simple rules, while at thesame time control the complexity and structure of the rule
to be generated.
Alphabet Indexing + Pattern Rule
Alphabet Indexing

1
2
3

R

1) 3212221222
2) 3222122213
3) ......

Amino Acid Sequences
Positive Examples

1) MARSLARTTTVRQP...
2) MASIRTGSRVSFKC...
3) ............
.....

Pattern

Positive Examples

A, C, F, G, I, L, S, T, W
D, E, H, K, M, N, P, Q, V, Y

Positive Examples‘‘212221’’1) TRUE2) TRUE3) ......

Negative Examples

Negative Examples

234) 3222222222
235) 3223321222......

234) FALSE
235) FALSE......

Cut interval [1, 10]

Negative Examples

234) MNSLSLSFTTALN...
235) NSFDVSRVSTKTS...
......

Positive Examples

Indexing sum1) 68.1
2) 68.4
3) ....
Negative Examples

Amino Acid Indexing (ZIMJ680104: Isoelectric point)

A
C
D
E
F
G
H
I
K
L
6.0 5.1 2.8 3.2 5.5 6.0 7.6 6.0 9.7 6.0234) 57.1
235) 59.6.....

Threshold63.3 < ?

Positive Examples

1) TRUE2) TRUE3) ......
Negative Examples

234) FALSE
235) FALSE......

M
N
P
Q
R
S
T
V
W
Y
5.7 5.4 6.3 5.7 10.8 5.7 5.7 6.0 5.9 5.7

Amino Acid Index Rule

Fig. 1. Concept diagram of amino acid index rule and alphabet
indexing + approximate pattern rule

Our search for the final hypothesis consists of two
main aspects: amino acid index, and alphabet indexing+ approximate pattern. The details of each aspect will bepresented in the following sections, but we describe thembriefly here (See Figure 1).
Amino acid index A large amount of experimental andtheoretical research has been performed to characterizedifferent kinds of properties of individual amino acids
and to represent them in terms of a numerical index.
The AAindex database (Kawashima and Kanehisa, 2000)
is a compilation of 434 of such indices. As noted in
the previous subsection, protein sorting signals havebeen characterized by the biochemical properties of theamino acids composing them, and it seems reasonable
to assume that some kind of characteristic which isimportant for protein sorting is already contained in the
AAindex database. Also, although an amino acid index
generally assigns a real number for each amino acid, itshould be easy for us to interpret the biological meaningof the rule when we find a “good” amino acid index
contained in AAindex, which helps greatly in explaining
the data. Therefore, using AAindex as a knowledge base,
we generate amino acid index rules.
Alphabet indexing + approximate pattern Again fromprevious studies, we know that there is no clear-cut consensus sequence concerning each of the sorting signals.
However, since there does seem to be a common structure for the same signals, we wish to somehow capture thisknowledge. Our approach here is to consider motifs whichallow more ambiguity by using alphabet indexing (Shimozono, 1999) and approximate patterns (Wu and Manber,1992) over the indexed sequence, similar to the BONSAI
system (Shimozono et al., 1994), which was successful in
discovering meaningful knowledge from amino acid sequences.
An alphabet indexing is a classification of charactersof an alphabet into a smaller set of characters, and canbe viewed as a discrete, unordered version of an aminoacid index. For example, we may divide the amino acids
into the two classes of hydrophobic amino acids andhydrophilic amino acids. Using this alphabet indexing,
we can view the amino acid sequence as a sequence of‘0’s (hydrophobic) and ‘1’s (hydrophilic), and search forpatterns (e.g. ’001001100’) contained in the sequences.
The outline of this paper is as follows: In the next
section, we define the basic concepts used in our methods.
We then show the results we have obtained from applying
our methods to the data. Finally, we discuss how the rules
we discovered may be interpreted.

SYSTEM AND METHODS
Amino Acid Index Rule
An amino acid index is a mapping from one amino acidto a numerical value, representing various physiochemical
299

H.Bannai et al.

and biochemical properties of amino acids.
Definition 1 (Amino acid index)
Let A denote the set of amino acids, and R the set ofreal numbers. For a given amino acid index I : A →R and amino acid sequence s = s1 s2 . . . sn (for i :1 . . . n, si ∈ A), let I(s) denote the homomorphism[|I(s1 ); I(s2 ); . . . ; I(sn )|], where [|;|] denotes a sequenceof values.
2
The AAindex Database (Kawashima and Kanehisa,
2000) is a compilation of 434 types of amino acid indices,which have appeared in various reports.
Definition 2 (Amino acid index rule)
An amino acid index rule (R1-rule) is defined by: anamino acid index I , a specified region of the aminoacid sequence s denoted by s[u, v], a function fw ∈{avg, maxavgw , minavgw }, and a threshold τ , where:
avg(I(s)) is defined as the average of the values ofsequence I(s), maxavgw (I(s)) is the average of a
substring of size w in I(s), which gives the maximum
value (i.e. max{I(s0 ) | s = xs0 y, |s0 | = w}), andminavgw (I(s)) is similarly the average of a substringof size w in I(s) which gives the minimum value (i.e.
min{I(s0 ) | s = xs0 y, |s0 | = w}). s[u, v] = su . . . sv
(1 ≤ u ≤ v ≤ n) for s = s1 s2 . . . sn .
A sequence is predicted “positive” by the R1-rule if
fw (I(s[m, n])) > τ and “negative” otherwise.
2
The parameters to be chosen are: I, u, v, f, w, τ , and thetask is to look for the best combination of the parameterswhich can distinguish between sequences of different
signals.
With R1-rules, we expect to capture the overall properties of N-terminal sorting signals.

Alphabet Indexing + Approximate Pattern RuleAn alphabet indexing (Shimozono, 1999) is a classification of characters of an alphabet. It is formally defined asfollows:
Definition 3 (Alphabet indexing)
An alphabet indexing ψ is a mapping from one alphabet
Σ to another alphabet Γ, where |Γ| ≤ |Σ|. For x =x1 x2 . . . xl ∈ Σl , let ψ(x) denote the homomorphismψ(x1 )ψ(x2 ) · · · ψ(xl ) ∈ Γl . We will call ψ(x), theindexed sequence.
2
Definition 4 (Approximate pattern)
An approximate pattern (Wu and Manber, 1992) is a string
which can match another string, allowing up to k errors(mismatch). The mismatch can consist of up to 3 types:
insertion (ins), deletion (del), and substitution (sub). We
will call the parameters k and the types of mismatches
300

allowed, the mismatch allowance of the approximate
pattern.
2
Definition 5
An alphabet indexing + approximate pattern rule (R2rule) is defined by: an alphabet indexing ψ , a specified
region of the amino acid sequence s denoted by s[u, v],
a pattern p, and mismatch allowance M . A sequence ispredicted “positive” if p matches somewhere in ψ(s[u, v])
within mismatch allowance M , and “negative” otherwise.
2
The parameters to be chosen are: ψ, u, v, p, M , and thetask again is to find the best combination of the parameterswhich can distinguish between sequences of different
signals.
With R2-rules, we expect to find locally specific characteristics concerning N-terminal sorting signals.

Data
The data used in our computational experiments was
obtained from the TargetP web-site† . These data consistof two data sets: plant and non-plant sequences. The plantdata set of 940 sequences contained 368 mTP, 141 cTP,
269 SP, and 162 “Other” (consisting of 54 nuclear and108 cytosolic) sequences. The non-plant data set of 2738
sequences contained 371 mTP, 715 SP and 1652 “Other”(consisting of 1214 nuclear and 438 cytosolic) sequences.
We basically follow the work on TargetP, considering
different predictors for plant and non-plant proteins. Also,
as in the composition of TargetP, we will first consider
binary predictors which just predict whether or not agiven sequence contains a specific signal. The knowledge
obtained from these binary rules is combined into a
decision list, to form a final rule. For each binary predictor,
we will call the sequences concerning the signal inquestion positive examples, and the sequences concerning
the other signals, negative examples.
Search Strategies
We extensively search for various parameters describedin the previous section. Since the size of the search
space for the combinations of different parameters ishuge, an exhaustive search is not feasible even with thepowerful computers which were available. We adopted
a mixture of heuristics and exhaustive search. Manydifferent combinations of the parameters as well as minutevariations in the heuristics were tried.
Combining the Rules To create a single rule predicting
the sorting signal for a given sequence, we combine
the binary rules generated for each sorting signal into
a decision list. The structure of the decision list is†

http://www.cbs.dtu.dk/services/TargetP/

Feature Detection of N-Terminal Sorting Signals

shown in Figure 2. The structure was determined greedily,
according to the “ease” of discrimination by the R1-rules,
which was stable for all training/test combinations.
From preliminary experiments, R1-rules seemed to be
sufficient for discriminating signal peptide sequences. As
for the other signals, neither type of rule seemed goodenough for identifying the signals. Therefore, we consider
combining both types of rules (R1-rules and R2-rules)
into a single rule. The first node of the decision list
discriminates signal peptides with a single R1-rule, while
the second and third nodes consist of both R1-rule andR2-rule. The two rules (or perhaps their negations) are
combined with a logical ‘and’ where a sequence is judged
to have a certain signal if both rules say so.
sequence

P1
P1
yes

SP?

SP

P2
P2
Other?

yes

Other

Omitted for non-plant

P3
P3
mTP?

no

yes

mTP

Fig. 2. The Structure of the
final rule for plant and nonplant data sets. The last nodein parentheses concerning cTP
and mTP is omitted for the
non-plant data set (classifying
to mTP). The various parameters such as the amino acidindex, substring intervals, alphabet indexing, and patterns
which were chosen in the 5
training runs are summarizedin Table 1 and 2.

cTP

Evaluation of Prediction Accuracy
The whole search space conducted in our search wasenormous, and involved considerable amounts of humanintervention, influenced largely by human intuition. To
give a fair estimate for the prediction accuracy of our
methods, we choose a modest range of parameters tosearch for in the cross validation, and show that theknowledge discovered is fairly stable even in that quite
large range.
Training and Evaluation We follow the training andevaluation methods used for TargetP. The data wererandomly divided into 5 equal sized datasets by dividing
each subset of sequences with specific localization sites
into 5 datasets. Rules were generated by using 4 of thedata sets as training data, and testing was conducted on
the remaining data set. This was repeated for the 5 possible
pairs of training and test set, and the overall performanceis the sum of the 5 results. (All rules are generated by using
the training data set only.)
Preliminary experiments showed that R1-rules werefairly stable, but R2-rules seemed to somewhat over-fit thetraining data. To overcome this problem, in the training
phase for R2-rules, the training set was again randomly
divided into 5 sets (4 ttrain and 1 ttest sets), and rules are
generated from ttrain and tested with ttest. The arithmetic
product of the scores from the ttrain and ttest sets was used
to select which alphabet indexing and substring interval touse. The pattern was then trained using all sequences ofthe original training set, using the alphabet indexing andsubstring interval.
Rules are evaluated by the Matthews correlation coefficient (MCC) (Matthews, 1975), defined by:

tp × tn − f p × f np(tp + f n)(tp + f p)(tn + f p)(tn + f n)
where tp = true positives, f p = false positives, tn =true negatives, and f n = false negatives. Sensitivity,
the fraction of correctly predicted positive examples
tp( tp+f), and specificity, the fraction of true positives inntp
the examples predicted as positive ( tp+f), were alsopcalculated for reference.
Details of the search is given below:
Amino acid index rule Since we know that the signals
are located somewhere in the N-terminal region, welook (somewhat) exhaustively at the substring intervals
in this region: For amino acid index I , all 434 entries
in the AAindex Database together with 20 more entries,
assigning a value of ‘1’ to one amino acid and ‘0’ to therest were considered. For these 454 entries, 72 substringintervals [u, v] = [5n + 1, 5k] (where n = 0 . . . 8 andk = 1 . . . 8) were considered. For these 454∗72 = 32688
combinations, fw = avg, maxavgw , minavgw wereconsidered where w was taken to be 6 to 12, resulting in
32688 ∗ (2 ∗ 7 + 1) = 490320 combinations. For all these
combinations, all possible thresholds are considered for τ :let fw1 , ..., fwn be all fw values of n sequences in sorted
order. Then, τ = (fwi + fwi+1 )/2, i = 1, . . . , n − 1. The
combination of I, u, v, f, w, τ which gives the highest
MCC score is recorded.
Alphabet indexing + approximate pattern rule The substring intervals [u, v] is taken to be [5n + 1, 5n + 5k](where n = 0, 1, 2 and k = 2, 3, 4). For a given alphabet indexing ψ , all patterns of length 8 appearing inthe sequences are considered for p. The mismatch types
were limited to insertion and deletion only (no substitution). The maximum mismatch number was fixed at 2. We
started with the alphabet indexing classifying the aminoacids into three classes, according to their “charges”:(
0 if
x ∈ {D, E},
1 if
x ∈ {K, R},
ψ0 (x) =2 if x ∈ A − {D, E, K, R}
301

H.Bannai et al.

Combination of the rules After determining the parameters for the above rules, the rules and possibly their
negations are combined with a logical ‘and’, but a portionof the parameters are trained again. Namely, the substringintervals, f , window sizes, amino acid index, and alphabet
indexing are fixed. We retrain the mismatch allowance,
pattern, and threshold. Their ranges are expanded in theretraining: The maximum mismatch number of 1 to 3 wasallowed, and all patterns of length 5 to 10 appearing in thedata were considered. The top 100 R1-rules are combinedwith all possible R2-rules, and the combination which
gives the best MCC score is chosen to be used against thetest set.

IMPLEMENTATIONThe software used in our analysis was developed using
the Hypothesis Creator Library‡ (Bannai et al., 2001).
Various shared memory multi-processor computers wereavailable for calculation: 2 SGI Origin 2000 with (128,32) x 195MHZ R10000 processors, 1 Sun Ultra Enterprise
4500 and 2 Sun Ultra Enterprise 3500 with (14, 8, 8)x 400MHz Sun Ultra II processors respectively. Each isequipped with well over 2GB of memory, which was thelimit of the software.
RESULTS AND DISCUSSION
The parameters found for each training set is summarizedin Table 1 for the plant data set, and Table 2 for the
non-plant data set. The scores of the cross validation
is summarized in Table 3, together with the scores forTargetP written in parentheses (The scores for TargetP was
taken directly from (Emanuelsson et al., 2000)).
We can see that the MCC scores for our predictor isfairly close to those of TargetP, except for chloroplasttransit peptides (cTP). However, it should be notedthat our score for cTP (0.64) would rank second, after
TargetP (0.72), better than PSORT (0.51), MitoProt (0.44),‡

http://hypothesiscreator.net/

302

60
20

40

Frequency

80

100

120

Hydropathy Index of [1,30] − Max Average of Window size 110

and optimized the indexing by conducting a local searchon the alphabet indexing (Shimozono et al., 1994): i.e.
consider the alphabet indexings which are obtainedby changing the indexing for a single amino acid (40candidates in this case), and adopt the indexing whose
product of the MCC scores for ttrain and ttest is thehighest for the best pattern. The process is repeated until
a local maximum is reached. A local search strategy
was used because an exhaustive search for all possiblealphabet indexings would result in 320 combinations,which was not feasible. Numerous tries starting fromother alphabet indexings, which were chosen randomly,
were also conducted, but high scoring indexings seemed
to be centered around ψ0 .

−1

0

1

2

3

4

value

Fig. 3. Histograms (light-SP, dark-mTP, cTP, Other) of maxavg11
values of hydropathy index (Kyte and Doolittle, 1982) for thesubstring [1, 30] of the plant data set. The threshold was 2.07727.
We can see that there is a clear difference in the distribution.

and ChloroP (0.50) (Emanuelsson et al., 1999), in thecomparison of (Emanuelsson et al., 2000). Our predictor
scores higher for plant signal peptides, and for the othersignals, our scores would again rank second, after TargetPwith respect to the other predictors.

Biological Evaluation of the Rules
Amino acid index rules
SP vs (mTP + cTP + Other): [Node P1, rule R1 in
Table 1] The amino acid index with the highest score
was the hydropathy index (Kyte and Doolittle, 1982), andjudging from the substring interval [1, 30], and function
maxavgw where w is around 11, we can say this rule
corresponds to characteristics known for signal peptides(the hydrophobic h region) (von Heijne, 1990) (Figure3). What is surprising is that such a simple rule could
discriminate signal peptides so well - better than TargetP
for plant proteins.
(mTP + cTP) vs Other: [Node P2, rule R1 in Table
1] The amino acid index was “negative charge”, whichassigns a value of 1 to aspartic acid (D) and glutamic acid(E). This also corresponds to known characteristics: mTP
and cTP are rare in negatively charged amino acids (vonHeijne et al., 1989).
mTP vs cTP: [Node P3, rule R1 in Table 1] Various
amino acid indices were chosen, with substring regions
for a very short region at the N-terminal. However, theamino acid index: Isoelectric point (Zimmerman et al.,1968) can be considered as a more accurate measure of the
net amino acid charges. Atom based hydrophobic moment

Feature Detection of N-Terminal Sorting Signals

Table 1. The parameters chosen for each training set (threshold τ is omitted) for the plant data set. The nodes Pn corresponds to nodes in Figure 2.

Node Trial†

R1
Amino Acid Index [u, v]

R2
fw , dirAlphabet Indexing [u, v]

Pattern

Mismatch

Combination

P1

1
2
3
4
5

Hydropathy index1 [1, 30] maxavg11 , ↑Hydropathy index [6, 30] maxavg11 , ↑Hydropathy index [1, 30] maxavg11 , ↑Hydropathy index [6, 30] maxavg11 , ↑Hydropathy index [6, 30] maxavg11 , ↑not used
not used
not used
not used
not used

not used
not used
not used
not used
not used

not used
not used
not used
not used
not used

R1→SP
R1→SP
R1→SP
R1→SP
R1→SP

P2

1
2
3
4
5

Negative Charge [1, 25]
Negative Charge [1, 25]
Negative Charge [1, 25]
Negative Charge [1, 30]
Negative Charge [1, 30]

avg, ↓
avg, ↓
avg, ↓
maxavg8 , ↓avg, ↓

DE → 0, AR → 1, Other → 2 [1, 20]
DE → 0, CR → 1, Other → 2 [1, 20]
DE → 0, R → 1, Other → 2 [1, 15]
DE → 0, CR → 1, Other → 2 [1, 20]
DE → 0, CRF→ 1, Other → 2 [1, 20]221200020
20002212
0221202002222222
020222222

3 ins/del2 ins/del1 ins/del1 ins/del1 ins/del¬R1 ∨ R2→Other†¬R1 ∨ R2→Other¬R1 ∨ R2→Other¬R1 ∨ R2→Other¬R1 ∨ R2→Other

P3

1
2
3
4
5

Hyd. mom.2 [1, 10]
Isoelectric point3 [1, 10]
Hyd. mom. [1, 10]
Net charge4 [1, 10]
Isoelectric point [1, 15]maxavg6 , ↑avg, ↑
maxavg9 , ↑avg, ↑
maxavg12 , ↑E → 0, KR → 1, Other → 2 [1, 10]
E → 0, KRW → 1, Other → 2 [1, 10]
E → 0, ARW → 1, Other → 2 [1, 10]
E → 0, KR → 1, Other → 2 [1, 10]
E → 0, DKRW → 1, Other → 2 [1, 10]22112221
22110
22110
121222111221

2 ins/del2 ins/del2 ins/del2 ins/del2 ins/delR1 ∧ R2→mTP
R1 ∧ R2→mTP
R1 ∧ R2→mTP
R1 ∧ R2→mTP
R1 ∧ R2→mTP: The actual rule was R1 ∧ ¬ R2 → mTP or cTP

Table 2. The parameters chosen for each training set (threshold τ is omitted) for the non-plant data set. The nodes Pn corresponds to nodes in Figure 2.
R1
Amino Acid Index [u, v]

fw , dir

P1

1
2
3
4
5

Hydropathy index [1, 30]
Hydropathy index [1, 30]
Hydropathy index [1, 30]
Hydropathy index [1, 30]
Hydropathy index [1, 30]

P2

1
2
3
4
5

Net Charge [1, 25]
Negative Charge [1, 20]
Negative Charge [1, 20]
Negative Charge [1, 20]
Negative Charge [1, 20]

Node Trial

1

R2
Alphabet Indexing [u, v]

Pattern

Mismatch

Combination

maxavg12 , ↑maxavg12 , ↑maxavg12 , ↑maxavg12 , ↑maxavg12 , ↑not used
not used
not used
not used
not used

not used
not used
not used
not used
not used

not used
not used
not used
not used
not used

R1→SP
R1→SP
R1→SP
R1→SP
R1→SP

minavg12 , ↑avg, ↓
maxavg12 , ↓maxavg12 , ↓maxavg12 , ↓DE → 0, R → 1, Other → 2 [1, 25]
DE → 0, R → 1, Other → 2 [1, 25]
DE → 0, R → 1, Other → 2 [1, 30]
DE → 0, R → 1, Other → 2 [1, 25]
DEY → 0,R → 1, Other → 2 [1, 25]202020220
2211221222
2211221222
2212211222
22122212

3 ins/del2 ins/del2 ins/del2 ins/del1 ins/delR1 ∧¬ R2→mTP
R1 ∧ R2→mTP
R1 ∧ R2→mTP
R1 ∧ R2→mTP
R1 ∧ R2→mTP: Hydropathy index (Kyte and Doolittle, 1982), 2 : Atom based hydrophobic moment (Eisenberg and Mclachalan, 1986),

3,4: Net charge, Isoelectric point (Zimmerman et al., 1968).

fw ↑ means that rule will answer yes if the value of fw (I(s[u, v])) is above a certain value τ , fw ↓ is the opposite.

(Eisenberg and Mclachalan, 1986) is also a similar aminoacid index, where the values for arginine (R) and lysine(K) are higher than the other amino acids. Although values
for aspartic acid (D) and glutamic acid (E) are also higher
for the atom based hydrophobic moment, these aminoacids rarely appear in mTP or cTP, and do not effect the
average values.
Therefore, together with the interpretation from
(mTP+cTP) vs Other, we can see that both mTP and cTPlack negatively charged amino acids, but mTP tend to be
more positively charged than cTP for the front end of thesignal.
Also seen in the alphabet indexing + approximate
pattern rule for mTP vs cTP, the region which was best for
distinguishing the two signals seemed to be located in the
short portion of the sequences, whereas the best regions
for distinguishing the other signals tended to be a longer.
The plain occurrence count of amino acids did not seemto appear in any of the trials. This is perhaps because thenumber of certain amino acids is too rough an estimate of
the overall biochemical properties of the signals.

303

H.Bannai et al.

Table 3. The Prediction Accuracy of the Decision Lists (scores of TargetP (Emanuelsson et al., 2000) in parentheses). This represents the sum of the predictionsof the 5 hypotheses of Tables 1 and 2 over the test set.

Data Set

True
category

# of
seqs

cTP

Predicted category
mTP
SP

Plant

cTP
mTP
SP
Other

141
368
269
162

96 (120)25 (41)6 (2)8 (10)

26 (14)309 (300)
9 (7)17 (13)

0 (2)
4 (9)
244 (245)
2 (2)19 (5)
30 (18)10 (15)135 (137)

0.71 (0.69)

0.86 (0.90)

0.98 (0.96)

0.70 (0.78)

––
––
––

275 (330)
8 (13)
119 (152)

11 (9)
660 (683)
44 (49)85 (32)47 (19)1489 (1451)––

0.68 (0.67)

0.92 (0.92)

0.92 (0.97)

Specificity

Non-plant

mTP
SP
Other

371
715
1652

Specificity

Alphabet indexing + approximate pattern rules(mTP + cTP) vs Other: [Node P2, rule R2 in Table
1] The alphabet indexing was stable near ψ0 . The best
patterns were found to match the ’Other’ sequences, rather
than patterns matching mTP and cTP signals. Althoughpatterns of the latter type would be of more interest, thisis natural since mTP and cTP are different signals andthe similarity in their structure may be subtle. Looking
at the combination of the rules, a signal is rejected formTP or cTP if the sequence contains (nearly) consecutive’0’s, which is aspartic acid (D) or glutamic acid (E). The
occurrence of ’1’ in each pattern is limited, showing thatmTP or cTP signals should contain a number of arginine(R). Lysine (K) is classified to ’2’ perhaps showing theasymmetry of arginine and lysine (K) in mTP.
mTP vs cTP: [Node P2, rule R2 in Table 1] The best
patterns were found to match mTP sequences. Somepatterns may be too short to judge, but the patterns”22112221’ and ’1212221’ seem to be capturing theperiodic occurrence of arginine (R) or lysine (K) (‘1’) in
mTP, which is the characteristic of an amphiphilic α-helix(von Heijne et al., 1989).
With the same parameters, we also searched for thebest patterns which match cTP and do not match mTP.
The patterns found were ’022210’ for trials 1, 3, and 4,’2222022222’ for trial 2, and ’220222110’ for trial 5, allwith a maximum of 1 insertion/deletion. It is interestingthat all the patterns contain a ’0’, which is glutamic acid
(E).

304

Other

Sensitivity

MCC

0.68 (0.85)
0.84 (0.82)
0.91 (0.91)
0.83 (0.85)

0.64 (0.72)
0.75 (0.77)
0.92 (0.90)
0.71 (0.77)

0.74 (0.82)
0.92 (0.91)
0.90 (0.85)

0.67 (0.73)
0.90 (0.92)
0.78 (0.82)

Non-plant
A similar interpretation can be done for rules concerning the non-plant data set. The difference from theplant set being that the alphabet indexing was morestable around ψ0 . Also looking at the patterns discovered,
the first pattern “202020220” does not match mTP
sequences, meaning that mTP sequences are again rarein aspartic acid or glutamic acid. For the other patterns“2211221222”, “2212211222”, “22122212”, we cansee again the periodic occurrence of arginine (R) of anamphiphilic α-helix. The pattern seems to be more stablein the non-plant data set perhaps the data set is muchlarger than for the plant set.
Overall, the rules discovered can be interpreted in termsof biological knowledge known for the different signals.
The parameters chosen for the rules in each of the training
rounds seemed to be fairly stable, suggesting that the rules
are capturing relevant characteristics concerning the Nterminal signals.

Future WorkFor the plant data set, looking at the number of classified
sequences, the weakness of our predictor seems to lie
mainly in the discrimination of mTP and cTP. It would
be interesting to find another simple but different form ofrule to discriminate the two types of signals.
In the search we conducted, we defined the regions as
substring intervals, fixed for all the sequences. Although
the N-terminal signals are generally located in a somewhat
fixed area, this may not be true for nuclear sorting
signals, whose position in the sequence looks arbitrary.

Feature Detection of N-Terminal Sorting Signals

The substring interval may be “simple” for human tounderstand, but may not be simple for the molecules
detecting the signal. It would be desirable to find a way totarget the actual location of the signal, and then consider
the rules mentioned in this paper. If we are successful,there might also be ways to predict cleavage sites by
locating candidate areas, and finding some meaningfulamino acid index or alphabet index rule.

Conclusion
We extensively searched various attributes and theirsimple combinations and were successful in finding asimple and interpretable rule which could explain the data
set well. Despite their simplicities, the prediction accuracyof the rules were still competitive with the prediction
scores of TargetP, the best predictor in the literature.
An experimental WWW service for predicting
N-terminal sorting signals using a decision list
trained on the entire data set is provided at: http://hypothesiscreator.net/iPSORT/. The range of parameters
searched to make the rules for the web service is different
from that in this paper in that the alphabet indexing was
searched in a wider range. Also, only avg was considered
for fw . Other parameters were adjusted to give best crossvalidation scores.
Acknowledgements
This research was supported in part by Grant-in-Aid
for Encouragement of Young Scientists and Grant-in-Aid
for Scientific Research on Priority Areas (C) “Genome
Information Science” from the Ministry of Education,
Sports, Science and Technology of Japan.
REFERENCES
Bannai, H., Y. Tamada, O. Maruyama, K. Nakai, and S. Miyano(2001). Views: Fundamental building blocks in the process ofknowledge discovery. In Proceedings of the 14th International
FLAIRS Conference, pp. 233–238. AAAI Press.
Bruce, B. D. (2000). Chloroplast transit peptides: structure, functionand evolution. Trends Cell Biol. 10, 440–447.
Chou, K.-C. (2001). Using subsite coupling to predict signal
peptides. Protein Engineering 14(2), 75–79.
Claros, M. G. and P. Vincens (1996, November). Computational
method to predict mitochondrially imported proteins and theirtargeting sequences. Eur. J. Biochem. 241(3), 779–786.
Eisenberg, D. and A. Mclachalan (1986). Solvation energy inprotein folding and binding. Nature 319(6050), 199–203.
Emanuelsson, O., H. Nielsen, S. Brunak, and G. von Heijne (2000,
July). Predicting subcellular localization of proteins based on
their N-terminal amino acid sequence. J. Mol. Biol. 300(4),1005–1016.
Emanuelsson, O., H. Nielsen, and G. von Heijne (1999). Chlorop,a neural network-based method for predicting chloroplast transit
peptides and their cleavage sites. Prot. Sci. 8, 978–984.

Kawashima, S. and M. Kanehisa (2000). AAindex: Amino Acid
index database. Nucleic Acids Res. 28(1), 374.
Kyte, J. and R. Doolittle (1982). A simple method for displaying thehydropathic character of a protein. J. Mol. Biol. 157, 105–132.
Maruyama, O., T. Uchida, T. Shoudai, and S. Miyano (1998).
Toward genomic hypothesis creator: View designer for discovery.
In Discovery Science, Volume 1532 of Lecture Notes in Artificial
Intelligence, pp. 105–116.
Maruyama, O., T. Uchida, K. L. Sim, and S. Miyano (1999).
Designing views in HypothesisCreator: System for assisting in
discovery. In Discovery Science, Volume 1721 of Lecture Notes
in Artificial Intelligence, pp. 115–127.
Matthews, B. W. (1975). Comparison of predicted and observed
secondary structure of t4 phage lysozyme. Biochim. Biophys.
Acta 405, 442–451.
Nakai, K. (2000). Protein sorting signals and prediction ofsubcellular localization. In P. Bork (Ed.), Analysis of Amino
Acid Sequences, Volume 54 of Advances in Protein Chemistry,
pp. 277–344. San Diego: Academic Press.
Nakai, K. and P. Horton (1999). PSORT: a program for detecting
the sorting signals of proteins and predicting their subcellular
localization. Trends Biochem. Sci. 24, 34–35.
Nakai, K. and M. Kanehisa (1992). A knowledge base for predicting
protein localization sites in eukaryotic cells. Genomics 14, 897–
911.
Shimozono, S. (1999). Alphabet indexing for approximating
features of symbols. Theor. Comput. Sci. 210, 245–260.
Shimozono, S., A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara,
and S. Arikawa (1994). Knowledge acquisition from aminoacid sequences by machine learning system BONSAI. Trans.
Information Processing Society of Japan 35(10), 2009–2018.
von Heijne, G. (1990). The signal peptide. J. Membr. Biol. 115,
195–201.
von Heijne, G., J. Steppuhn, and R. G. Herrmann (1989). Domain
structure of mitochondrial and chloroplast targeting peptides.
Eur. J. Biochem. 180, 535–545.
Wu, S. and U. Manber (1992). Fast text searching allowing errors.
Commun. ACM 35, 83–91.
Zimmerman, J., N. Eliezer, and R. Simha (1968). The characterization of amino acid sequences in proteins by statistical methods.
J. Theor. Biol. 21, 170–201.

305