Clustering and Detection of 5' Splice Sites of mRNA byk Weight Matrix Model

Katsuhiko Murakami 12Toshihisa Takagi 1katsu@ims.u-tokyo.ac.jp

12takagi@ims.u-tokyo.ac.jp

Human Genome Center, Institute of Medical Science, University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan
Central Research Laboratory, Hitachi, Ltd.
1-280, Higashi-Koigakubo, Kokubunji-shi, Tokyo 185-8601, Japan

1 Introduction
Biological signals on DNA sequences such as TATA box, GC box, CAAT box, the Shine-Dalgarno
sequence in the promoter regions, and splice sites (donor/acceptor sites) in eukaryotic mRNA areof considerable interest because they play numerous crucial roles in binding with proteins, or RNA.
Recently it has been suggested that the 5' splice site recognition is performed in vivo through a
combination of several rules which are still unclear [1].

2 Materials and Methods
The data we used was obtained from the GENSCAN training/test sets as described in reference [1].
We extracted both the actual and pseudo 5' splice sites from the data with the GT-AG rule (most ofthe introns start with GT and end with AG).
Biological signal sequences are traditionally characterized by the positional weight matrices (PWMs)
introduced by Staden [2]. In this method, given an uncharacterized
short sequence X = x1 ; x2 ; :::; x ,P
the score of the sequence is calculated by the formula: S (X ) = =1log(P (i; x )); wherei2
P (i; x ) is the probability of generating the nucleotide x at position i for the site model under consideration. Here, a PWM is de ned as a matrix which is constructed from P (i; x ) for all i; x .
In this work, we clustered the actual 5' splice sites using the PWM. The process of clustering sites
is similar to the k-means clustering algorithm [3]. The rst step in our clustering algorithm is to create
two PWMs, which are constructed from all the positive data (authentic sites) and all the negative data(pseudo sites) respectively. Some PWMs (called random PWMs) are also constructed from random
weights for each class, except the above two classes. Second, all positive data is distributed to theclasses in such a way that the PWM of the class generates the distributed sequences with the highest
probability among the classes (data distribution). Third, a new PWM is constructed for each classwith the distributed data. Fourth, the each random PWM is modi ed slightly so that the random
PWM is closer to the target PWM in the class (training). The data distribution procedure and training
procedures of the PWMs are iterated. During the iteration, the score function T is maximized at eachstep, where T is de ned as:
P P  S (X )T =P =2 P =1 P=
log(P (i; x ));=2=1 =1 i 2Pwith the constraints i =P (i; x ) = 1 for all position i. X is a sequence of the training data,and  is the delta function:
npii:::n;xA;C;G;TiiixkNlkmNl;mlmil;m =mA;C;G;Ti

A;C;G;Tl;mp;xn(ll;mm

1 if X belongs to the class l0 otherwise:
m282ii3 Results and Discussion
We have clustered the 5' splice sites into several classes. Each class was represented by the PWMs.
Table 1 shows the motifs extracted from the PWMs. The characters are typed in upper case if theprobability is more than 50%. If the probability is more than 35%, they are typed in lower case. The`-' indicates the exon-intron boundary. The motifs of class 2 to class 5 are new and di erent from thetraditional consensus sequence (C1: a/cAG-GTa/gAGt).
Table 1: Consensus sequences extracted from the PWMs in the classes.
class -3-2-1 | +1 +2 +3 +4 +5 +6C1 a/c A
G | G T a/g A GtcC a/t | G T a/G A G TC2C3AA
G | G TAA G T
D g/T G | G T a/G A G T
C4C5cAG | G TAA G a/g
We applied the extracted PWMs for splice site detection. The speci city at di erent sensitivity
levels are calculated for the test set. The speci city (SP) is de ned using True Positive (TP) and False
Positive (FP) by SP = + . At the threshold level in which 20% of actual sites are detected, thespeci city of the traditional PWM was only 50%, while that of our method was 52%. We observed
especially high speci cities for classes 2, 3, and 4 (59%, 57%, and 57%).
TPTPFP

Acknowledgements
This work is partially supported by Grant-in-Aid for Scienti c Research on Priority Areas, \Genome
informatics" from the Ministry of Education, Science, Sports and Culture, Japan.

References[1] Burge, C. and Karlin, S., Prediction of complete gene structures in Human genomic DNA, J. Mol.
Biol., 268:78{94, 1997.
[2] Staden, R., Measurements of the e ects that coding for a protein has on a DNA sequence andtheir use for nding genes, Nucleic Acids Res., 12:551{567, 1984.
[3] Ripley, B.D., Pattern Recognition and Neural Networks, Cambridge University Press, 1996.

283