Wei Liu
email: yzliuwei@126.com

Ling Chen
email: lchen@yzcn.net

An Efficient and Fast Algorithm for Mining Frequent Patterns on Multiple Biosequences

Keywords: Biological sequence, Frequent Pattern Mining, Primary Patterns

Mining frequent patterns on biosequences is one of the important research fields in biological data mining. Traditional frequent pattern mining algorithms may generate large amount of short candidate patterns in the process of mining which cost more computational time and reduce the efficiency. In order to overcome such shortcoming of the traditional algorithms, we present an algorithm named MSPM for fast mining frequent patterns on biosequences. Based on the concept of primary patterns, the algorithm focuses on longer patterns for mining in order to avoid producing lots of short patterns. Meanwhile by using prefix tree of primary frequent patterns, the algorithm can extend the primary patterns and avoid plenty of irrelevant patterns. Experimental results show that MSPM can achieve mining results efficiently and improves the performance.

Introduction

Biosequence patterns usually correspond to some important functional (or structural) elements [START_REF] Brejova | Finding Patterns in Biological Sequences[END_REF] such as conserved sequence patterns, repeated patterns or combinative patterns etc. Hence it is very significative to find such patterns in protein family analysis, transcriptional regulation analysis, and genome annotation etc. The task of biosequence pattern mining [START_REF] Bajesy | Survey of biodata analysis from a data mining Perspective[END_REF] is also the key technique for gene recognition, biosequence functional prediction and interactions explanation between sequences. It is one of the most important research areas in biosequence data mining.

In the area of data mining, lots of sequential pattern mining algorithms have been proposed in recent years. At present the sequential pattern mining algorithms are mainly classified as two categories: one is for frequent patterns mining on single sequence; the other is for mining in multiple sequences. The former can mine frequent patterns only for single sequence [START_REF] Mannila | Discovering generalized episodes using minimal occurrences[C][END_REF][START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF] , and is unable to synchronously analyze the relation between frequent patterns from a certain sequence and those contained in the other sequences. Such analysis is common and necessary in biosequence data mining. For the latter, according to the definition [START_REF] Agrawal | Mining sequential patterns[END_REF] by Agrawal and Srikan in 1995 based on the analysis of transaction data: given a sequence set and a user-specified support threshold, the problem of sequential pattern mining is to find all frequent subsequences, that is to say, the counts of the subsequence appeared in the sequence set are not less than the minimal support threshold. In 1996, Strikant et al. proposed GSP (generalized sequential pattern mining) [START_REF] Srikant | Mining sequential patterns: Generalization and performance improvements[END_REF] which introduced the concept of time and level-wise constraints based on Apriori algorithm. It mines all frequent patterns by the use of bottom-up and breadth-first search strategy. But when the sequence database is a large-scale one, large amount of candidates could be produced and the database should be frequently scanned. Especially when the sequences contain long patterns, large amount of short candidate patterns may be generated , which could cause the problem would be intractable and of lower efficiency. In order to solve this problem, in 2000 Pei et al. put forward an algorithm named Prefixspan [START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefix-projected growth[END_REF] based on pattern growth approach. It adopts divide and conquer method and continuously produces much smaller projected databases so as to mine frequent patterns. Since no candidates are produced in the algorithm, search space is greatly reduced. Its main cost is on the construction of projected databases and its performance is much higher than Apriori-based algorithms. Other recent works on sequential pattern mining algorithms have been surveyed in [START_REF] Han | Frequent Pattern Mining: Current Status and Future Directions[END_REF] by Han et al.

However, because of the particularity and variety of mining requirements for biological data, the previous developed methods can not be applied directly to the large-scale biological data mining. Therefore extensive efforts have been devoted to developing some special mining algorithms for biological data, such as PTR-based algorithms [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[C][END_REF] by Apostolico et al., ATR-based algorithms [START_REF] Delgrange | STAR: An algorithm to search for tandem approximate repeats[END_REF][START_REF] Kolpakov | Finding repeats with fixed gap[C][END_REF][START_REF] Kolpakov | Finding approximate repetitions under hamming distance[END_REF][START_REF] Krishnan | Exhaustive whole-genome tandem repeats search[END_REF][START_REF] Kurtz | REPuter: The mani fold applications of repeat analysis on a genomic scale[J][END_REF][START_REF] Landau | An algorithm for approximate tandem repeats[J][END_REF][START_REF] Hertz | Identifying DNA and protein patterns with statistically significant alignments of multiple sequences[END_REF][START_REF] Pevzner | Combinatorial approaches to finding subtle signals in DNA sequences[END_REF] by Delgrange et al. and TRFinder algorithm [START_REF] Benson | Tandem repeats finder: A program to analyze DNA sequences[END_REF] by Beason. Later Kurtz presented REPuter [START_REF] Kurtz | REPuter: The mani fold applications of repeat analysis on a genomic scale[J][END_REF] algorithm based on suffix tree which overcame the limitation of the length of input sequences. It was based on sequence alignment technique but could hardly find those frequent repeats among DNA sequences. In 2007, Wang et al made researches on searching for the similar repeated segments [START_REF] Wang | Finding LPRs in DNA sequence based on a new index SUA[C][END_REF] and then introduced a new criteria of similarity and the concept of SATR(segment-similarity based approximate tandem repeats). They designed an algorithm SUA_SATR [START_REF] Wang | SUA-Based algorithm for finding SATRs in DNA sequence[END_REF] based on SUA with no limitations on pattern length during the searching process. Moreover, with the same similarity, the algorithm is faster than other traditional algorithms for the same DNA sequence, although its efficiency should be improved. In 2007 Xiong et al. proposed BioPM algorithm [START_REF] Yun | BioPM: An Efficient Algorithm for Protein Motif Mining[C[END_REF] specially for protein sequence mining. They introduce the concept of multiple supports so as to overcome the disadvantages of traditional algorithms and improve its performance and efficiency. But when the minimal support becomes lower, it can not keep its high efficiency since numerous projected databases are constructed. In addition, the algorithm still produces large numbers of irrelevant short patterns during the mining process. In 2009, Guo et al. addressed MBioPM algorithm [START_REF] Shun | A new pattern mining algorithm for protein sequences[END_REF] which is an improvement of BioPM algorithm. Based on a pattern partitioning scheme, the algorithm successfully avoids constructing large amount of projected databases. But when the lengths of the patterns exceed k, it requires a large buffer for frequent patterns mining which resulted in huge memory space cost. Moreover, it also takes large amount of time to align the existing patterns with those in the buffer. All these large time-space costs will cause the low efficiency of the algorithm.

To overcome the problems of traditional sequential pattern mining algorithms mentioned above, we present a fast and efficient algorithm named MSPM for multiple biosequence mining. The algorithm mines all frequent patterns rapidly based on the prefix tree of primary frequent patterns which reflects more biological meanings. Our empirical studies on the tested data from pfam protein database show that MSPM algorithm can obtain higher performance and efficiency than the traditional mining algorithms.

2

Definitions and Concepts Lemma 3 For a string S, the average length of the primary patterns with respect to all characters in S will be not more than () CS .

Proof: From lemma 2, we know that the summation of the lengths of all the primary patterns of S satisfies

()1 ()() x x xCSi n iCSS s ∈= ≤•

∑∑

. Furthermore, by lemma 1 we also know that the number of total primary patterns of S is equal to S. Therefore the average length of all the primary patterns of S will be not more than () CS .

Q.E.D From the lemmas mentioned above, we can see that all primary patterns can be intercepted in () S Ο time by scanning S. The framework of the algorithm for intercepting the primary patterns is described as follows:

Algorithm Intercept(S) Input: string S; Output: the primary patterns of S; begin For every ()

xCS ⊆ do k=1; () x k s =∅;
Let the first position of x appeared in S be l;

{ } ()() xxl kk sss = U i = l ; repeat While ( ) ii x ss ≠≠∅ U do { } ()() xxi kk sss = U ; i=i+1; End while k=k+1 ; { } () xi k ss = ; i=i+1; Until i s =∅

End for End

The table of primary patterns

After getting all primary patterns of S, we can further build a table of primary patterns for S. All the primary patterns are listed in the table in the lexicographic order so as to conveniently search.

Example 2 For the sequence "" Sbacaabcbab = in example 1, after sorting all primary patterns of S, the table of primary patterns can be built as shown in Table 1. s is the primary pattern and loc denotes the start position of m s in S.

Table1
All the primary patterns obtained by algorithm intercept(S) should be sorted so as to be arranged in lexicographic order. By Lemma 1, we know that there are S patterns. Suppose that Sn = , it costs ( ) Obviously by lemma 3 we know that the average length of primary patterns is not more than ∑ and their length is imbalance. Because of each pattern with different lengths, the traditional radix sorting algorithm can't be applied straightforwardly. Therefore, we present the following sorting algorithm.

log
Algorithm2

Merging the Primary Pattern tables

After getting all primary pattern tables of multiple sequences, we can merge them in order to obtain a merged primary pattern table as shown in Table 3.

Table3. The merged primary pattern s is the primary pattern and Seq denotes the sequences where m s appears.

The primary frequent patterns mining

Definition 2(Distribution support [START_REF] Yun | BioPM: An Efficient Algorithm for Protein Motif Mining[C[END_REF] ):Given a set of biosequences D and a subsequence T , the distribution support of subsequence T in D is defined as _sup()|{|,}| disDTssDTs =∈⊂ , which is the number of strings in D containing the subsequence T.

Definition 3: A primary pattern P is called a frequent primary pattern if dis_supD(P)≥ mindis_sup, where positive integer mindis_sup is the minimum support.

By the above definitions, we can build a frequency table for a string set D. For instance the frequency table for primary patterns of string set D in Example 3 is as shown in Table 4.. Let dis_sup be 2, and then based on Table 4, we can easily mine all primary frequent patterns: a(frequency: 4), ab(frequency: 4), abc(frequency: 3), ac(frequency: 3), acb(frequency: 2); b(frequency: 4), ba(frequency: 3), bc(frequency: 4); c(frequency: 4), cb(frequency: 4),cba(frequency: 3),cbab(frequency: 2).

Table4. The frequency table for primary patterns on multiple sequences

Based on above primary frequent patterns and table2, we can easily build the following two-dimension table respect to primary frequent patterns on multiple sequences.

Table5. The two-dimension table of primary frequent patterns on multiple sequences

Sequence Frequent patterns S 1 S 2 S 3 S 4 a {1,5} {1,5} {4} {1,4} ab {1} {5} {4} {4} abc {1} ∅ {4} {4} ac {5} {1} ∅ {1} acb ∅ {1} ∅ {1} b {2,4} {3,6} {1,3,5} {3,5} ba {4} ∅ {3} {3} bc {2} {3} {5} {5} c {3,6} {2,4} {2,6} {2,6} cb {3} {2} {2} {2} cba {3} ∅ {2} {2} cbab ∅ ∅ {2} {2}
The element { } 12 , ,..., k lll in the table denotes the set of starting positions of primary pattern in S. For example, the element {1, 5} in the first row of table5 denotes the primary pattern "a" are respectively in the 1 st and 5 th positions of S 1 . Furthermore, we can build the following table similar to Table1: s is a primary pattern and loc_set denotes the set of start positions of m s in each sequence.

3 The Prefix Tree of Primary Patterns

Aggregation Vector and Its Operations

To mine all the frequent patterns in a given biosquence set, a prefix tree is used. In order to fully comprehend the construction process of the prefix tree, first we give the following definitions. Definition 4: Let ( ) 12 , , ... , n T TTT = be a vector, where i T is a set, we call T is an aggregation vector.

Definition 5: Given an aggregation vector T, its support function D(T) can be defined as the number of nonempty sets in T, that is: ( )

( ) { } ;1 ii DTTTin =≠∅≤≤ .
The starting position set E (d) on the node d defines assigned as the starting position set of strings in T i ; Node-extend(T i , d i ); End if End for End for End Let the primary patterns table of D be D(H), the prefix tree of primary patterns of D can be built by calling the recursive process Node-extend(D(H), root).

Example 4 For the frequent primary patterns in Table 6, the prefix tree of primary frequent patterns by the above recursive algorithm can be built as shown in Fig. 1. ) (b i E is the terminative positions set of the substring corresponding to the i th string. Listing all characters on the edges of each path from the root to each leaf, one primary frequent pattern can be obtained.

Mining Algorithm

The Generic Frequent Patterns Mining

The limitation of primary frequent pattern is that there is no same character as the first character in the pattern. The primary frequent pattern table on multiple sequences mentioned above can only mine primary frequent patterns, but can not mine all the frequent patterns. We can use the prefix tree of frequent primary patterns to mine larger frequent patterns by aggregation vector operations on the vectors at each node. For example, in Fig. 1 the frequent pattern"cbabc" can be obtained by expanding the primary frequent pattern "cbab". After getting the prefix tree as fig. 1, we can easily find the path of pattern "cbab" and then its terminative node vector ( ∅ , ∅ , {6}, {6}) also can be obtained at the leaf. Next we return to the root of the tree and perform intersection operations respectively on the starting node vectors of the root's sons and the terminative node vectors of the primary pattern. For instance in fig. 1, after the intersection operation on the child c , ({3,6}, {2,4}, {2,6}, {2,6})∩( ∅ , ∅ , {6}, {6})=( ∅ , ∅ , {6}, {6}), its support is 2. This means the pattern is frequent. Therefore we can expand frequent pattern"cbab" by the operation { } { } { } cbabccbabc ∪= and a longer frequent pattern"cbabc" is obtained. From the analysis mentioned above, based on the prefix tree of primary frequent patterns we propose an algorithm named Span(s, E (s) , a) for mining all frequent patterns. It is a recursive process. The algorithm starts from the root and extends patterns for each node level by level. The framework of the algorithm Span(s, E (s) , a) is as follows: Algorithm 4:Algorithm Span(s, E (s) , a) Input: a: the node where a is; s: the string that be extended;

E ( s ) = ()()()

2

 2 ...." ikikik sss ++-the k th primary pattern of S with respect to x. definition, we can easily get the following lemma. Lemma 1 For a string S, let its character set be () CS ⊆∑. For an () xCS ∈ , suppose there arex n primary patterns with respect to x in S, For a string S, summation of the lengths of the primary patterns with respect to all characters in () CS will satisfy:

2

 2 In table4, each entry is denoted as ( ), m Freq s, where m s is a primary pattern and Freq denotes the distribution support of m s in the set of multiple sequences D.

Fig. 1 .T

 1 Fig.1. Prefix tree of primary frequent patterns for D In the prefix tree shown in fig.1, each character x in the edge denotes the character or substring that the node represents, { } 12 , ,..., k lll denotes the set of starting position sets of primary patterns with the prefix of x in D. Each inner node b stores a starting node aggregation vector T ) (b = ()()() 12 {,,...,} bbb k TTT , where ) (b i T is the starting positions set of the substring corresponding to the i th string. Each leaf node b stores a node-depth b D . Moreover, there are a start-node aggregation vector T ) ( b = ()()() 12 {,,...,} bbb k TTT and a terminative node aggregation

12 {F

 12 ,,...,} sss k EEE : the terminative vector set of s; Freq-set: the set of frequent substrings; mindis-sup : the minimal support threshold; Output: the Freq-set after update Begin For each child b of a do Assuming that the starting vector of b is T on edge (a, b) is x. If b is not an leaf node then num=0; For i= 1 to k do ()() bs iii FTE =∩ ; If i ≠Φ then num=num+1; endif End for Assuming that the set is 12 {,,...,} k FFFF = If disminsup num ≥then If x ≠∅ then Freq-set=Freq-set {} sx ∪ * ; Span (,,) sxFb * ; Else Span (,,) sFb ; End if

.

  The table of primary patterns for s

	Num	s	m	loc
	1	a		4
	2	ab	9
	3	abcb	5
	4	ac	2
	5	b		10
	6	ba	8
	7	bacaa	1
	8	bc	6
	9	caab	3
	10	cbab	7
	In the table, each entry is a vector (			)

, , m Numloc s , where Num is the index of the entry in the table, m

Table 2 .

 2 Table2. The primary pattern table of four sequencesThe primary pattern table of S 1

		Sort( m s , '' m s )
	Input: m
	then according to the initial characters of all patterns in m s , we can divide them into
	some buckets as	12 , , ... , mmml sss ;
	' s =∅ m
	For i=1 to l do
		After emitting the first character of mi s , we can get a new string set ' mi s .
	Delete all the empty strings from	' s . mi
	If	' s =∅ then ''' mi mmmi sss =∪	End if

s : the primary patterns of S; Output: '' m s : the ordered primary patterns table;

Begin

Let the initial character of mi s be i x and l =∑. If there is 12 ... l xxx <<< in ∑ ,

  table of multiple sequences

	Num	s	m	Seq
	1	ab	2
	2	abc	3,4
	3	abcb	1
	4	ac	1
	5	acb	4
	6	acbc	2
	7	b	2
	8	ba	3,4
	9	bac	1
	10	bc	1,3,4
	11	bca	2
	12	c	1,3,4
	13	cab	2
	14	cb	2
	15	cba	1
	16	cbab	3,4
	In Table3, each entry is denoted as a vector (	)

, , m NumSeq s , where Num is its index in the table, m

Table 6 .

 6 The primary frequent pattern table of D

	Num	S m		Loc_set
	1	a	{1,5}, {1,5}, {4}, {1,4}
	2 3 4 5	ab abc ac acb	{1}, {5}, {4}, {4} {1}, ∅ , {4}, {4} {5}, {1}, ∅ , {1} ∅ , {1}, ∅ , {1}
	6 7	b ba	{2,4}, {3,6}, {1,3,5}, {3,5} {4}, ∅ , {3}, {3}
	8	bc	{2}, {3}, {5}, {5}
	9	c	{3,6}, {2,4}, {2,6}, {2,6}
	10 11 12	cb cba cbab	{3}, {2}, {2}, {2} {3}, ∅ , {2}, {2} ∅ , ∅ , {2}, {2}
	In Table 6, each entry is denoted as a vector (	, Numlocset s , _ m	)	, where Num is
	the index of this entry in the table, m

, , ... , n

Acknowledgement: This research was supported in part by the Chinese National Natural Science Foundation under grant No. 60673060, Natural Science Foundation of Jiangsu Province under contract BK2008206.

The Prefix Tree Construction of Primary Frequent Patterns

By algorithm 2 can not only sort the primary patterns, but also can obtain the number of each primary pattern. And during the recursive process, the number of primary patterns with the prefix of substring y can also be obtained. By summing up the numbers of the primary patterns with the prefix of a certain character or substring y, the scope [ ] , lu of those primary patterns in the sorted primary pattern table can also be computed. Therefore, while implementing algorithm 2, we can also expediently construct a prefix tree of primary patterns.

Definition 9 For a table of primary patterns, its corresponding prefix tree is a rooted tree. The path from the root to each leaf denotes a primary pattern and each edge in the path denotes a character. Children of the same node denote different characters.

Once the prefix tree is construced, all the primary pattern can be obtained by listing all characters in sequence of each path, one.

From the definition of the prefix tree, we can design an algorithm for building the prefix tree of primary patterns. It is a recursive process. The algorithm repeatedly builds the prefix subtree for the nodes from the root to the leaves level by level. Therefore, we present an algorithm named node-extend (S, d) which constructs a prefix tree rooted as d for the set S of primary patterns. The framework of the algorithm node-extend is shown as follows.

Algorithm3:Algorithm node-extend(S, d); Input: S: the set of primary patterns and their starting positions in the alphabetical order table. Each primary pattern in S takes the form of(s, e)which denotes an entry of the primary pattern table, where s is a primary pattern and e is the starting position set of s. d : the node to be extended. mindis-sup: the minimal support threshold; Output: the prefix tree rooted at d for the set S of primary patterns; Begin Suppose there are r different first characters in the strings of S; then the strings of S can be divided into r groups according to their first characters; Let the group with the first character x i be S i ;

For i= 1 to r do T i =Ф; For all strings P of S i do Emit the first character x i of P and obtain a string P';

End for End

Based on algorithm 4, we present an algorithm Freq-Mining for mining frequent patterns on the string set S.

Algorithm 5: Algorithm Freq-Mining(S,root) Input: S: the strings for mining;

root: the root of prefix tree of primary sub-patterns for S; Output: Freq-set: the set of frequent pattern of S;

MSPM Algorithm

In this section, we present algorithm MSPM(Multiple Sequential Pattern Mining for Biological Data)for mining the frequent patterns in a biosequence set S. Algorithm MSPM first mine all frequent primary patterns. Then these frequent primary patterns can be extended to get all the frequent patterns. Framework of algorithm MSPM is as follows.

Algorithm MSPM(S, minloc_sup) Input: S ; an biosequence set; mindis_sup: the minimal support threshold; Output: Freq-set : the set of all frequent patterns; Begin For each biosequence

End for Merging all primary pattern tables of multiple sequences and sorting all patterns by calling algorithm 2; Building the frequency table of primary patterns and getting set H of all primary frequent patterns; Building the two-dimension table respect to frequent primary patterns and then the frequent primary pattern table of S can be obtained;

Constructing the prefix tree T of frequent primary patterns by calling the recursive algorithm Node-extend( S(H), root); Freq-Mining(S,root); End.

Experimental Results and Analysis

To test the efficiency of our algorithm MSPM, we made an experiment on two groups of data for comparisons. In the experiment of first group, the traditional Apriori algorithm, BioPM algorithm, MbioPM algorithm and our algorithm MSPM are tested to compare their performance. The experimental results show that the change of minimal support threshold makes a slight impact on our algorithm MSPM. The test on the second group compares the computation times of algorithm BioPM, MbioPM algorithm and MSPM to validate that our algorithm is more effective and faster than other ones under the same minimal support threshold.

Test Data and Computational Environment

All testing data in the experiments are from pfam protein database ( http://pfam.sanger.ac.uk/ ) , and the average length of our selected protein sequences is 1000 [START_REF] Bateman | The Pfam Protein Families Database[J][END_REF] which ensures the experimental validity. All experiments were conducted on a 3.00GHZ Pentium 4 with 2.00GB memory. All codes were complied using Microsoft Visual C++6.0.

Comparison of the Performance

The purpose of the first group experiment is to prove that the change of minimal support threshold makes a slight impact on our algorithm MSPM. We took protein sequence samples from three protein families ( G-alpha, Calici Coat, Glyco_hydro_19)of pfam database as testing data. During the process of experiment, we chose 50 protein sequences with the similar length respectively from three protein families as a testing data set so as to ensure the diversity of the test data. With each specified support, we tested 50 sequences using three algorithms. Fig. 2 shows the running time of algorithms Aprior [START_REF] Srikant | Mining sequential patterns: Generalization and performance improvements[END_REF] , BioPM [START_REF] Yun | BioPM: An Efficient Algorithm for Protein Motif Mining[C[END_REF] , MbioPM [START_REF] Shun | A new pattern mining algorithm for protein sequences[END_REF] and MSPM for the same biological data set with different minimal supports. From fig. 2 we can see that four algorithms becomes faster when the minimal support increases. But MSPM algorithm is rather stable and always faster than the other three ones especially with the lower minimal supports. That is because with lower minimal supports, Apriori algorithm would produce more short candidate patterns which necessarily result in the growth of computation time and inefficiency. Similar to Apriori, the inefficiency of BioPM algorithm is caused by the fact that it must spend more time in frequently building projective databases. MBioPM algorithm mines from the patterns with a certain length but it takes large amount of time for comparing the existing patterns with the patterns in buffer zone. While MSPM uses primary patterns with longer length for mining, which avoids producing lots of short patterns and more candidates. Through the merging operation and pattern growth method based on the prefix tree of primary frequent patterns, the algorithm can accelerate mining procedure. The above analysis shows that our algorithm MSPM is more efficient, stable and faster.

Comparison of the computational Time

We test the algorithms on the second data group to compare their computational time with the same minimal support threshold. The experimental results show our algorithm MSPM is more effective. We took protein sequence samples with the similar length respectively from ten protein families ( Globin, short chain dehydrogenase, SBP_bac_9, Acety-ltransferase, GNAT family, ATPase family, Glyco_hydro_19, G-alpha, Calici coat, Birna VP2)of pfam database. We fixed the minimal support as 15%, and compared the computational times by the algorithms BioPM, MBioPM and MSPM on data sets consisting of different number of sequences from 100 to 600. Fig. 3 shows the comparison of their computation times. It can be observed from fig. 3 that the running speeds of three algorithms become slower when the number of sequences increases. But the MSPM algorithm is rather stable and always faster than other two algorithms. The reason is BioPM algorithm produces lots of short patterns during the process of iterations at first and then frequently builds projective databases. All of these operations will necessarily increase the time cost of the algorithm. MBioPM algorithm mines from the patterns with a certain length but it takes large amount of time to align the existing patterns with the patterns in buffer zone when mining the k-length frequent patterns. It also repeatedly creates or eliminates buffer zone during the process of pattern growth. All of these cause the algorithm be less efficient. MSPM mines frequent patterns from primary patterns with longer length, which avoids producing lots of short candidate patterns and reduces the computation time. The merged operation and pattern growth based on the prefix tree of primary frequent patterns also avoid producing the redundant patterns and greatly improve mining efficiency of our algorithm.

Conclusion

Based on the mining requirements and characteristics of biosequential patterns, we present an efficient and fast algorithm MSPM for multiple biosequence mining. The algorithm first builds multiple primary pattern tables according to all primary patterns of multiple sequences. Then through merging operation, the corresponding merged primary pattern table can be obtained. Based on this merged primary pattern table, all primary frequent patterns can be easily mined. Furthermore, we also present an algorithm for general frequent patterns mining on multiple sequences. The algorithm constructs a prefix tree of primary frequent patterns based on primary frequent patterns table and thereby mines all frequent patterns rapidly by the use of aggregation vector operations on the prefix tree. During the process of pattern growth, the algorithm neither produces any candidates nor constructs a mass of projective databases. This makes our mining results reflect more biological meanings and also improves mining efficiency. Our empirical studies on the tested data from pfam protein database show that MSPM algorithm can obtain higher performance and efficiency than the traditional mining algorithms.


Peng Zhao

Yuanyuan Shi

Xinming Ma
email: xinmingma@126.net

Shuping Xiong

Dynamic Modeling on Nitrogen Assignment in Tobacco

Keywords: Tobacco, Nitrogen, Assignment, Model

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Tobacco is one of the important cash crops. Nitrogen is the most significant nutritious element to tobacco, and it has remarkable influences on tobacco's growth and development as well as yield and quality. Either insufficiency or redundancy of nitrogen affects the output and quality of tobacco. An appropriate supply of nitrogen can ensure the normal growth of the plant and the premium yield of tobacco leaves as well as good quality of the leaves [START_REF]China Tobacco Cultivation[END_REF][START_REF] Chunjian | Nitrogen management and its relation to leaf quality in production of flue-cured tobacco in China(in Chinese)[END_REF][START_REF] Collins | Principles of flue-cured tobacco production[END_REF][START_REF] Xiaolei | Effect of Different Nitrogen Formson Tobacco Quality Indices(in Chinese)[END_REF]. The distribution of nitrogen in the whole plant is of great significance; it directly influences the quality of tobacco leaves. The proportion of distribution of nitrogen in root, stem and leaves is leaves﹥stem﹥root. Different growing positions of leaves can directly affect the whole content of nitrogen [START_REF] Liu Weiqun | Influence of Different Nitrogen Levels onYield,Quality ,Dry Matter and Nitrogen Accumulation and Distribution of Flue-cured Tobacco(in Chinese)[END_REF]. The total accumulation of the amount of nitrogen of leaves in different leaf positions is middle leaves﹥upper leaves﹥lower leaves [START_REF] Chengxi | Studies on Nitrogen Absorption and Utilization in Tobacco(in Chinese)[END_REF]. During the maturity process of flue-cured tobacco, the nitrogen accumulation amounts and distribution proportion of stem increase and the nitrogen accumulation amounts and distribution proportion of leaves decrease [START_REF] Xinghua | Studies on Nitrogen Absorption, Distribution and Utilization in Flue-cured Tobacco under Higher and Lower Fertility Conditions(in Chinese)[END_REF].

In the field of crop, visual simulation models of crops have been developed. The models can also simulate nitrogen dynamic. There are CERES, ORYZA and WHEATGRO at abroad [START_REF] Ritchie | CERES-WHEAT[END_REF][START_REF] Drenth | O-RYZA simulation modules for potential and nitrogen limited rice[END_REF][START_REF] Aggarwal | Analyzing the limitations set by climate factors ,genotype , water and nitrogen availability on productivity of wheat I. The model description , parameterization and validation[END_REF]. In China, GaoLiangzhi [START_REF] Liangzhi | Rice cultivational simulation-optimizationdecision making system(RCSODS)[END_REF] has developed RCSODS; Cao Hongxin [START_REF] Hongxin | Studies on simulation-optimization-decision making for wheat population,soil moisture and nitrogen dynamic[END_REF] has explored simulation-optimization for wheat population, soil moisture and nitrogen dynamic. Predecessors mainly focus on wheat, corn and rice, but seldom focus on tobacco. Based on the dynamic simulation of tobacco's absorption and distribution of nitrogen, this research aims to provide scientific foundation for the improvement of the quality of tobacco through the appropriate utilization of nitrogenous fertilizer.

Materials and Method

Materials

The materials of the research mainly come from experimental research in the fields, relevant literature and consult to tobacco experts. They are mainly used to fix the parameter of the model and to verify the model.

Field experiments

Experiment Ⅰwas carried out from 2004 to 2005 in Science and Education Institute of HAU. The tested variety was Zhongyan101. It was sowed on March 5 th , and transplanted on May 1 st . The tested soil was sandy soil. The proportion of the organic substance of the soil was 0.89%; the content of the nitrogen was 0.669g•kg -1 ; the content of available phosphorus was 14.25mg•kg -1 and the content of available potassium was 70.21mg•kg -1 . pH value was 8.1. The tobacco was cultivated in pots. Each pot was filled with 30kg dry soil. The amounts of nitrogenous fertilizer were set at three levels: 0kg•hm -2 , 45kg•hm -2 and 90kg•hm -2 . The amounts were repeated three times and 30 plants were dealt with at one time. In the nitrogenous fertilizer, the proportion of nitrogen in nitric form and in ammonium form was both 50%; the amounts of P 2 O 5 and K 2 O were respectively 45kg•hm -2 and 90kg•hm -2 . KHNO 3 and (NH 4 ) 2 SO 4 were used as nitrogenous fertilizer; Ca(H 2 PO 4 ) 2 was used as phosphate fertilizer and KHNO 3 and K 2 SO 4 were used as potash fertilizer. Experiment Ⅱwas carried out in Fenchen Town, Xiangcheng County, Henan Province. The tested variety was Zhongyan101. It was sowed on March 1 st and transplanted on April 25th. The growing method was the same as Experiment Ⅰ. The tested soil was sandy clay. In the soil, the proportion of the organic substance was 1.25%; the content of nitrogen was 0.925g•kg -1 ; the content of available phosphorus was 16.24mg•kg -1 and the content of available potassium was 78.46mg•kg -1 . pH value was 7.6.

Measuring method

The means of measuring the whole content of nitrogen in tobacco plant: to take the roots, stems and leaves of the tested tobacco at the respective periods of 30days, 45days, 60 days 75days, 90days and 105days after transplantation. Then dried at the temperature of 105℃ and the content of nitrogen in the roots, stems and leaves measured by semi-microkjeldahl [START_REF] Shidan | Soil and Agricultural Chemistry Analysis[END_REF].

The Description of the Model

The description of the absorption of nitrogen by roots

The nitrogen tobacco needed was mainly absorbed by roots. The model didn't take other ways of absorption such as leaves spraying into consideration. Supposing all the nitrogen was absorbed by roots.

The total uptake of nitrogen equalized the crop ' s minimum requirement for nitrogen plus the small supplier of nitrogen in the maximum amount of soil.

TNUP=MIN(NDEML+NDEMST+NDEMRT, ANSL/DELT)

(

ANSL represented the available nitrogen in the soil; ANSL/DELT stood for the total available nitrogen in a time step; DELT in the model was usually one day. The available content of nitrogen in the soil on the first day after growing was as follows: Initial available nitrogen in the soil was ANSL(0)=ANSL0+AFA×FNC×RF. ANSL0 represented available nitrogen in the soil without utilizing nitrogenous fertilizer; AFA represented the amount of nitrogenous fertilizer not utilized; FNC represented the content of nitrogen in the nitrogenous fertilizer; RF represented the ratio of the utilization of the fertilizer. ANSL0 can be calculated by the dynamic model of nitrogen's circulation in the soil; it can also be fixed by statistics from experiment in the fields. The latter means is easy and direct. The method was using the content of nitrogen absorbed by the whole plant during the whole growing period without using fertilizer to divide the whole days of the growing period. The model was as follows: . Nu represented the content of nitrogen absorbed during the whole growing period in the soil without utilizing fertilizer. Dsum represented the whole days of the growing period.

The description of the distribution of nitrogen

The nitrogen absorbed by the root was distributed to root, stem and leaves. The quantity of nitrogen absorbed by the plant was changing with its growing periods. What's more, the whole content of nitrogen that the organs held was different in different growing periods. Thus the whole content of nitrogen that contained by different organs was in obvious evolutionary patterns.

Supposing the whole content of nitrogen absorbed by root from the soil was distributed according to the requirement of the organs, then index of distribution in the organs was as follows:

NCPL=NDEML/(NDEML+NDEMST+NDEMRT) (2)
NCPST=NDEMST/(NDEML+NDEMST+NDEMRT)

NCPRT=NDEMRT/(NDEML+NDEMST+NDEMRT)

NCPL represented the index of distribution of nitrogen in the leaves; NCPST represented the index of distribution of nitrogen in the stem; NCPRT represented the index of distribution of nitrogen in the root; NDEML represented the content of nitrogen required by the leaves; NDEMST represented the content of nitrogen required by the stem and NDEMRT represented the content of nitrogen required by the root.

The accumulation ratio of the content of nitrogen of each organ was calculated through the index of distribution of nitrogen in the organ multiplied the whole content of nitrogen absorbed by the root(TNUP, kg• hm -2 • d -1 ). The formula was:

NUPL=TNUP×NCPL (5) NUPL=TNUP×NCPL (6)
NUPRT=TNUP×NCPRT [START_REF] Xinghua | Studies on Nitrogen Absorption, Distribution and Utilization in Flue-cured Tobacco under Higher and Lower Fertility Conditions(in Chinese)[END_REF] NUPL stood for the accumulation ratio of the content of nitrogen in the leaves; NUPST stood for the accumulation ratio of the content of nitrogen in the stem and NUPRT stood for the accumulation ration of the content in the root. Then the amount of nitrogen required by each organ at any time was :

NDEML=(WLV×XNCEL-ANLV)/TC (8)
WLV, WST, and WRT were net weight of the leave, stem and root. XNCST, XNCST and XNCRT were the maximum nitrogen volume (kg N/kg non-carbon substance) of the leave, stem and root, respectively which vary with different growing periods. ANLV, ANST and ANRT were the actual nitrogen volume of the leaves, stem and root. TC was the corresponding time coefficient which was usually one day in the model of plant growing. XNCL was the model's input coefficient. XNCST and XNCRT can be ascertained by the following formulas:

XNCST=0.5×XNCL (9)
XNCRT=0.5×XNCST [START_REF] Aggarwal | Analyzing the limitations set by climate factors ,genotype , water and nitrogen availability on productivity of wheat I. The model description , parameterization and validation[END_REF] Based on the empirical data of the year 2004 and 2005(Table 1), and considering the influence of tobacco plant's nitrogen situation on the index of nitrogen distribution, the dynamic distribution index of tobacco plant's nitrogen situation was simulated.

Table 1. The change of nitrogen distribution index .

The Model's Exploration Tool and Operation Environment

The system was developed on the operation stage of Windows 2000 with PIV 1.8GCPU and 256MB internal memory. The software of Access 2003 was used to design data basis, the dominant part and user interface of Chinese version Visual Basic 6.0. The system was configured by auto structure software. Each constituent part can be used either separately or linked with other component parts flexibly and conveniently. All these made the system interface concise and clear and easy to be operated.

Verification of the Model

According to the physical and chemical properties together with the cultivation condition of the soil in Zhengzhou City and Xiangcheng County, first, the module of the distribution of nitrogen was used to simulate the distribution of nitrogen in the whole plant during the growing period, both the tobacco in Zhengzhou and the tobacco in Xiangcheng were used to simulate. The study selected Zhongyan101 as the representative, making a comparison between simulation and observation of root nitrogen rate. showing that the simulation and observation of root nitrogen rate fit well through the model.

Table2. Comparison between simulation and observation of root nitrogen rate(kg• hm -2 ).

Table 3 showed the comparison between simulation and observation of stem nitrogen rate. It can be worked out that X 0.05 , 5 2 =9.89>Xc 2 (0.1760,0.1681), which revealed that at thelevel of 0.05, the differential value was not significant; that is to say, the simulation and observation of stem nitrogen rate fit well through the model. According to the test method of 1:1 charting, figure 1 compared the simulated value and the observed value with the leaf nitrogen content as representative, and calculated their correlation coefficient. The result showed that the correlation coefficient between simulation and observation of tobacco leaf nitrogen rate was 0.9934. They were in good consistency.

Table3. Comparison between simulation and observation of

Conclusion

The whole growing period of tobaccos needs many nutritional elements, among which the demand for nitrogen is great. The supply of nitrogen directly influences the Simulation data(Kg.hm growth, yield and quality of tobacco. The dynamic simulation of nitrogen is a major part of crop growth simulation [START_REF] Yun | A Review on the Development of Crop Modeling and its Application[END_REF][START_REF] Weixing | System Simulation and Intelligent Management for Crops[END_REF][START_REF] Shiming | Agroecosystem Analysis[END_REF][START_REF] Shun | Experimental Researches and Dynamic Modeling on the Partitioning Index of Nitrogen in Rice(in Chinese)[END_REF][START_REF] Xinming | Design and Implementation of a Knowledge Model System for Tobacco Nitrogen Strategies(in Chinese)[END_REF]. The nitrogen accumulations in roots, stems and leafs change with different growing periods. Simulating the distribution of nitrogen in tobacco plant could help us understand and learn the nitrogen content of each organ of tobacco plant. Therefore, we can adjust the amounts of nitrogenous fertilizer utilized in time and improve the yield and quality of tobacco.

Through the quantitative measurement of tobacco in different growing periods, this research concludes the pattern of tobacco's absorption of nitrogen. Establishing the nitrogen absorption and distribution models which are in dynamic changes following different growing periods can simulate the nitrogen content in each organ of tobacco plant at different growing periods. With the comparison between the simulated and observed value and their insignificant difference at the level of 0.05 shows the simulated and observed value of nitrogen contents in roots, stems and leaves of tobacco by the model are in good consistency. With the 1:1 figure comparison between the simulated and observed value with nitrogen content of tobacco as representation and their correlation coefficient at 0.9934 demonstrate they are consistent well. Therefore, this model is better in decision-making and adaptability and could forecast and guide the administration of nitrogenous fertilizer in the tobacco fields.

What needs explanation is that this model is the nitrogen distribution model of tobacco without consideration of the lost nitrogen following the defoliation of tobacco leaves in the late period of growing. Only by adding blade decaying rate in our later deeper researches can we describe the nitrogen content of tobacco during the whole growing periods more accurately.

Fig. 1 .

 1 Fig. 1. Comparison between simulation and observation of leaf nitrogen rate.

Table 2

 2

	showed the comparison between simulation and observation of root
	nitrogen rate. It can be worked out that X 0.05 , 5	2 =9.89>Xc 2 (0.2992,0.3875),
	which revealed that at the level of 0.05, the differential value was not significant;

  stem nitrogen rate.

	is to say, the simulation and observation of leaves nitrogen rate fit well through the
	model.
	Table4. Comparison between simulation and observation of leaf nitrogen rate.
			Xiangcheng Xiangcheng			Zhengzhou Zhengzhou
	Day after translate Day after translate Prediction Observation Differential Prediction Observation Differential value data value value data value	Xc 2 Prediction Observation Differential Xc 2 Prediction Observation Differential value data value value data value	Xc 2 Xc 2
	30 30	1.1 13.01	1.07 13.03	0.03 -0.01 0.0182 14.07 0.2068 0.84	0.8 14.08	0.04 -0.01 0.0169 0.2642
	45 45	3.69 33.81	3.62 33.84	0.07 -0.03 0.0065 33.16 0.0521 3.28	3.19 33.18	0.09 -0.03 0.0067 0.0518
	60 60	12.68 52.22	12.56 52.27	0.12 -0.05 0.0038 60.92 0.0117 11.15	11.14 60.97	0.01 -0.05 0.0034 0.0218
	75 75	11.72 55.53	11.77 55.71	-0.05 0.0173 10.2 -0.19 0.0018 54.98	10.21 54.76	-0.01 0.0237 0.22 0.0015
	90 90 105 105 Xc 2 Xc 2	13.91 58.64 15.22 43.65	14.01 58.99 15.67 43.12	-0.1 -0.35 0.0004 59.81 0.0112 9.29 -0.45 0.0002 -0.53 0.0245 -0.2992 0.0552	9.28 59.5 --	0.01 0.31 --	0.0006 0.0260 --0.3875 0.0290
			Xiangcheng			Zhengzhou
	Day after	Prediction Observation Differential Xc 2 Prediction Observation Differential Xc 2
	translate
		value	data	value		value	data	value
	30	2.25	2.25	0	0.1129 2.31	2.3	0.01	0.1024
	45	6.64	6.66	-0.02 0.0348 4.69	4.66	0.03	0.047
	60	21.83	21.86	-0.03 0.0102 23.49	23.44	0.06	0.0084
	75	25.64	25.63	0.02	0.0092 22.59	22.69	-0.1	0.0072
	90	40.25	40.23	0.02	0.0056 42.2	42.34	-0.14 0.0031
	105	47.01	47.13	-0.11 0.0032	-	-	-	-
	Xc 2				0.176				0.1681
	Table 4 showed the comparison between simulation and observation of leaves
	nitrogen rate. It can be worked out that X 0.05 , 5	2 =9.89>Xc 2 (0.0552,0.0290),
	which revealed that at the level of 0.05, the differential value was not significant; that

Acknowledgements

This study has been funded by invitation to tender project of China State Tobacco Monopoly Administration (Contract Number: 110200201005)


Zhangchi
email: zhangc@nercita.org.cn

Chen Tian'en

Chen Liping

A Precision Subsidy Management System for Strawberry Planting in ChangPing distinct of BeiJing

Keywords: IC card, subsidy of agricultural materials, precision management, agricultural products safety

The misuse of pesticide and fertilizer take a great pollution to the agricultural environment, which seriously affects the quality and safety of agricultural products. The government put forward a series of policies of subsidy to lead the farmers to proper pesticide application and scientific farming. But the effect doesn't turn out as it wished to be because of the backward implementation methods and Stat methods. This research provides a Precision Management method for effectively managing subsidies for agriculture. Based on Non-contact IC card, the authors developed a Precision Management System for agricultural related subsidies management. This system was applied in one center and eleven experiment stores in ChangPing district in Beijing and solved problems like poor instruction for planting, tardy in subsidies providing and inaccurate information of stat during the strawberry growing season. Through this system, farmers can get the subsidies and instruction at the moment they buy agricultural materials, government can obtain the accurate data, and then adjustment the policies in time to get the desired effect.

Introduction

Agricultural pollution has been neglected for a long time due to the high environmental capacity, low level of industrialization, and low population density in rural areas in China. Excessive fertilization, sole-nutrient fertilization and overdose of nitrogenous fertilizer lead to problems like imbalance of soil nutrient, low utilization ratio of fertilization and agricultural environmental pollution. Shoddy fertilizers induce decline of agricultural product quality, even threaten people's life security [START_REF] Baogang | Prevention and Control of Fertilizer Pollution on Environment[END_REF] . According to State Environmental Protection Administration, agricultural pollution occupies as high as 1/3-1/2 of the total amount of nationwide pollution [START_REF] Yanzhong | On Agricultural Pollution in China[END_REF] . Thus, scientific farming and reduction of agricultural pollution is the key point to realize agricultural sustainable development strategy. Local governments has taken many measures to solve this problem, such as grant subsidies to recommended agricultural implements in order to standardize agricultural tools and set up agricultural technical advice station to provide information for scientific farming and rational maturing. These instrumentalities remarkably increase the quality of agricultural products and bring down the agricultural pollution, but there is deficiency. Most of the subsidies are released by the end of a year, that is, the allowances are mostly granted after the crop planting period. On the one hand, farmers can not get the subsidies in time; on the other hand, local governments can not get accurate information of requirement of agricultural means of production. Aiming to solve this problem, this paper provides a precision management method based on non-contract IC card. Assembling government administrative department, agricultural implement agency and farmers together, the authors developed a precision management system based on non-contract IC card to ensure that all the subsidies could be granted in time and that feedbacks could be send back in time. This system was applied in one center and eleven agencies in strawberry planting areas in ChangPing district in Beijing and proved to be efficient.

System analysis and design

Requirement Analysis

Whether information about subsidies of agricultural materials and scientific farming can be conveyed to the farmers precisely will directly affect the agricultural environment and the quality and safety of agricultural products. Meanwhile, the subsidies arriving in time or not will affect farmers' enthusiasm for planting. Based on this, the primary goal of our system is to set up a platform among the government administrative department, agricultural sales departments and farmers in order to pass the information about subsidies of agricultural materials and scientific farming to farmers precisely. Also through this system, providing of subsidies will become more timely and efficient, as a result, farmers' enthusiasm of planting will be enhanced to a great extent. Our government conducts the subsidies of agricultural materials aiming to ensure the quality of agricultural products and improve agricultural environment. So the subsidies of agricultural materials have to be managed precisely and provided in time so as to ensure the effective implementation of this beneficial policy. For this reason, another function of this system is to provide a tool using which the government can manage the subsidies of agricultural materials precisely. At the same time, by applying this system, related department can achieve a statistical analysis of the information about subsidies of agricultural materials so as to help the government make good policies, and to speed up our agricultural development in the end.

System structure

To meet the actual requirement, the system consists of six parts such as management subsystem, store subsystem, leader view subsystem, a centre database, several store databases and a huge number of IC card. Due to the different network condition in the agents, the whole system is designed in a telescopic C/S structure, through the VPN(virtual private network), each subsystem can connects to each other out of the network condition limited. All agencies submit the sale information to the centre database at a fixed time, consequently, the reliability and stability of the system can be ensured. The leader-view subsystem adopts a B/S structure; leaders can get the real-time information of subsidies anywhere through the browser.

The Major Business Process

According to the procedure of strawberry production in ChangPing distinct, the management subsystem inputs the first batch of data based on the land distributiton data and the details of subsidy. Adopt the mechanism 'one farmer one card', each farmer gets a IC card with his name, account, quota of subsidy, permit time and the printed growing instructions. In accordance with the latest information of subsidy download from the management subsystem, the payment for agricultural materials is made up of two parts, the one is cash part, paid by farmers, the other is subsidy, deducted from the IC card. Stores take a record of each transaction, and submit the records to management subsystem in a fix time. The management subsystem achieves a statistical analysis of the distribution process and using circumstances about subsidies of agricultural materials through these records. Based on the results of the statistics, government can adjust subsidy policy in time and then play a better role in guiding. Growing instructions in the card Fig. 2 the major business process of Precision Management System for the subsidy of agricultural materials

The Key Technology

Real-time Performance of the system

The major problems to be solved in the system are how to distribute subsidy in time and accurate statistics the data of subsidy. IC card of non-contact type (M1) is used, the farmer's name, account, balance, subsidy freeze, distribute date, commencement date, check date, ending date, card status and growing instructions are stored in the sectors of IC card. When farmer buy the agricultural materials, store subsystem calculates the total price and the subsidy should be distributed, subsidy bill is deducted from IC card, the balance is paid in cash. Store subsystem save the details such as account, name, price, number, cash, subsidy, serial and assistant into store database with status "0" when each transaction is finished. Store subsystem checks the records periodically, while finding records with status "0", immediately submits these records to management subsystem and updates the status with "1".Though this, the subsidy can be distributed in time and data of subsidy can be accurate statistics.

System Security

The whole system is a distributed system. In the server aspect, adopts the dual module hot spare(DMHS), if one server is crash down, System can switches to another server automatically in two minutes, which guarantees the security of database. In the data interaction aspect, set up a virtual private network, each subsystem has a multiple verification mechanism and all data is delivered unidirectional, which ensure the security of the data.

System Implementation

Management Subsystem

Considering the factors of development efficiency, interface effects and user demand, we used Visual C # as the development language, under the Visual Studio 2005 environment, combined with ESRI's ArcGIS Engine 9.3 SDK for system development. After comprehensive consideration of the data security, operating efficiency and system extension, chose SQL Server 2005 as the data base. Management sub-system was comprised of three function modules including the IC card management module, information maintenance module and data query statistics module. It is precisely the information publish and integrate centre of the precision management system for the subsidy of agricultural material, which provides IC card and growing instructions for farmers, recommended agricultural materials and subsidy information for agencies, accurate statistical data of subsidies for the government departments.

Store Subsystem

As a bridge between the government and farmer, the store subsystem complete the whole transaction processes. The distribute store subsystem acquires the information of the recommended agricultural materials and related subsidies information from the management subsystem and then transmit to the farmer. Store subsystem distributes subsidies to farmers as soon as they buy the agricultural materials with agricultural subsidies IC card, and then saves the detailed information for each transaction. Every store uploads the transaction data to the central database periodically to summary, aiming to query and stat.

Leader View Subsystem

Leader view subsystem provides a rich query and statistical functions. User can query the grant general progress of agricultural subsidies with the conditions of area, kind and time, the detailed circumstances of agricultural subsidies granting and agricultural products using the conditions of town, month / quarter and agricultural materials' name. All results are compared in different dimensions and displayed in graphs and tables. Analyzing these results, the management department of government can know the farmers' demand and subsidies grant progress roundly.

4、The Application

Finishing the development work of the precision management system, it takes the agricultural materials management department of ChangPing district in BeiJing as the center, set up eleven experiment agencies in the towns like Xingshou, Xiaotangshan, Baishan, Shahe, Machikou, Cuicun, Five thousands farmers are benefited for it. the system adopts the mechanism of ' one farmer one card ' to realize unified management on agricultural materials' recommendation, purchase, sale and subsidies of the whole district, making a connection between sale and subsidy of the agricultural materials, realizing the accurately recording of sale information, the real-time summarizing of the subsidy data and the timely distribution of subsidy, integrating the resource of strawberry grow effectively, mobilizing the energies of farmers and Guaranteeing the quality of agricultural product at the same time, laying the foundations of the development of strawberry industry in ChangPing district.

Conclusion

To meet the needs of precision management of granting subsidies during strawberry planting, this paper designed and developed a precise managerial system of subsidies supervision. Employing modern communication technology, this system built an information alternation platform among government administrative department, agricultural implement agency and ordinary farmers. Based on noncontract IC card, this precise system of subsidies supervision could send the statistic feedback in time; the farmers could promptly receive the subsidies and get guidance of scientific planting from the government. As a management system controlling the inception of agricultural material investigation, this project achieved the traceability of agricultural material during strawberry planting; reduced pollution caused by absurdness fertilizer application and consequently ensured the quality of agricultural production.

Fig. 1

 1 Fig.1 the structure of Precision Management System for the subsidy of agricultural materials

  Fig 2 is the major business process of Precision Management System for the subsidy of agricultural materials.

  Fig 3 shows the card distribution interface of management sub-system.

Fig. 3

 3 Fig.3 card sending page of the management subsystem.

  Fig 4 is the sale page of store subsystem.

Fig. 4

 4 Fig.4 sale page of store subsystem

  Fig 5 is the statistics page of the leader subsystem.

Fig. 5

 5 Fig.5 subsidy statistics by month page of the leader subsystem.


Qiang Han

Wenxing Bao

A Halal & Quality Attributes Driven Animal Products Formal Producing System Based on HQESPNM

Keywords: Halal, Quality, Traceability, Petri Nets, HQESPNM

Usually, halal animal products formal producing system consists of several components that cover major stages including Pre-processing, Processing and Post-processing. In this paper, we present five information systems to implement fundamental functions of formal management, scientific foods management, animal epidemic disease diagnose and prevention, processing standardization and market management, which respectively map to those components mentioned above. As halal animal products formal producing system, there are Halal & Quality attributes existing in all of the five information systems. Thereby, concentrated and systematic controlling of Halal & Quality attributes could improve whole quality of the producing system and ensure products is halal. Addressed to the problem of controlling scheme, first, this paper given a Halal & Quality Elements Extended SPN Model (HQESPNM) in detail. Second, it propose Platform-Independence architecture of the formal producing system based on HQESPNM through infrastructure of database integrate middleware. Finally, this paper given an Electronic-Agriculture Services case through Platform-Specified Software based on SOA to certificate that the model proposed by this paper is feasible for halal animal products system.

Introduction

At the beginning of 80's of last century, based on the Petri Net [START_REF] Petri | Kommunkation mit automaten[END_REF], Molly presented Stochastic Petri Net through associating a stochastic delay time to every transition from ready-to-fire to firing [START_REF] Molly | Discrete time stochastic Petri nets[END_REF]. With the development of science, computation science based on high-performance computing becomes more and more important [START_REF] Cui Huan-Qing | MPI Programs' Petri Net Model and Its Dynamic Properties[END_REF].As the Stochastic Petri Net presented, it was used in many applications of modeling, analysis and efficiency test, such as communication protocols, workflow design etc.

However, Stochastic Petri Net is not suitable to each application aspect completely. For example, to the formal producing and quality certification of Halal Animal, except general elements of normal management are suitable to Stochastic Petri Net for information system modeling and computation, the type of its Halal and Quality elements affection to all of steps in whole management process is through controlling the process and not by any time-element or stochastic-element. Once the Halal and Quality elements are destroyed in the management process, the products have not any meaning for Moslem people and other people.

Including all the animal product producing process of Pre-processing, Processing and Post-processing, in breeding, propagate, feed, fattening, slaughtering, transportation and market circulating, how to guarantee the products are processed under an consistency environment according to Halal and Quality standard, is the key of information system which service for this aspect.

To solve the problem above, this paper proposed an approach through combination technique [START_REF] Qiang | IEEE proceedings of the 2009 International Conference on Computer and Computing Technology Applications in Agriculture[END_REF] of Place expanding Petri nets [START_REF] Qi Fang-Min | A Modeling Method of Software Project Management Based on Petri Nets[END_REF] and Stochastic Petri Net [START_REF] Molly | Discrete time stochastic Petri nets[END_REF], and by the approach, this paper given a Halal & Quality Elements Extended SPN Model (HQESPNM) in detail. The primary thought of the approach is separate the problem of the aspect into two part, the part about general performance computation can be solved by Stochastic Petri Net, and the other part about Halal & Quality elements can be solved by Place expanding Petri nets. So that, by this means, through the function of the two Petri net theories, the problem of the aspect can be solved successfully.

In the detailed scheme of the halal animal products formal producing system model based on HQESPNM, this paper mainly given design of the model which separate Halal & Quality attributes into independent subsystem, and the implementation of its algorithm.

The organization of the remainder of this paper is as follows. Section 2 given the basic concepts and notations, and system model is given in section 3. Section 4 discussed how to use the system to solve the problem through an example. Finally, section 5 summarized the main results and points out the future work. The word "iff" means "if and only if" in this paper.

Basic concepts and notations

The concepts and notations of Petri nets are derived from some documents [START_REF] Peterson | The Theory of Petri Net and System Simulation[END_REF][START_REF] Murata | Petri Nets: Properties,Analysis and Applications[END_REF][START_REF] Chongyi | The Principles of Petrinet[END_REF][START_REF] Chuang | Stochastic Petri Nets and System Performance Evaluation[END_REF][START_REF] Huiqin | Study of the Normal Generalized Stochastic Petri nets and its Application in Testing System[END_REF][START_REF] Vazquez | Stochastic Continuous-State Approximation of Markovian Petri Net Systems[END_REF].

Stochastic Petri Net

Definition 1 A Petri net is a four-tuple     0 ; , , M F T P such that:
(1) P is a finite set of places, and T is a finite set of transitions, and

       T P T P , ; (2)
    P T T P F     is a set of arcs; (3)   ,... 2 , 1 , 0 : 0  P M is the initial marking. Generally, T P x    , the preset of x is     F and T P y y x    x y, | .



, and the post-set of x is

    F and T P y y x    y x, | .  and . . x x  is the spanning-set of x. If       F P T T P T T P P   1 1 1 1 1 1 1 F and ,          1 1 1 1 , ,
M F T P is called safe iff 1 ) ( , ), ( 0      p M P p M R M is satisfied. Definition 3 For a Petri net   ) ; , , ( 0 M F T P , ), ( ) ( ), ( ' ' 0 M R M for M R M if M R M     then M is called a home state.  is a reversible net system if 0 M is a home state. Definition 4   ) ; , , ( 0 M F T P is a Petri net.
 is said to be:

(1) weakly live iff

T t M R M     ), ( 0 such that  t M[ . (2) live iff * 0 , ), ( T T t M R M        such that   t M M [ [ '  . Definition 5   ) , , ; , , ( 0 W K M F T P is a Place/Transition Net, where: (1) ) ; , , ( 0 M F T P is a Petri net. (2)       N S K : is Place Capacity function. (3)   N F W : is Arc Priority function. ( 4
) ) ( ) ( : 0 p K p M P p    . Definition 6   ) , , , ; , , ( 0  W K M F T P is a continuous-timed Stochastic
Petri Nets, where:

(1)

) , , ; , , ( 0 W K M F T P is a Place/Transition Net. (2) ) , , , , ( 3 2 1 m        is set of transition average fired rate. i  is transition average fired rate of T t i  , which represent the fired times of i t in an unit time.               otherwise p M F p t F t p p M F p t F t p p M p M ), ( ) , ( ) , ( , 1 ) ( ) , ( ) , ( , 1 ) ( ) ( '

Place expanding Petri Net (PePN)

Based on the introduction of Petri Nets and Stochastic Petri Nets above, we can calculate performance data through modeling system. However, in the actual application of it, because of the dynamic change properties of modeling objects, the capacity of description for them is limited. So some researchers presented Place expanding Petri Net Models, example Place expanding Petri Net [START_REF] Qi Fang-Min | A Modeling Method of Software Project Management Based on Petri Nets[END_REF].Its definition is:

Definition 7   ) ; , , ( 0 M F T P
is a Place expanding Petri Net(PePN) , where:

(1) S={s|s is Place expanding Petri Net or Based on the HQESPNM, we can find that the correctly systematically running of Np has to be controlled under Nh and Nq through F . Then this paper given the system architecture and algorithm to implement HQESPNM as follow.

' ' , S S s  is place sets of  . (2) F z y S z T y S x F y x          ) , ( , : ) , ( . (3) F x z T z S y T x F y x          ) ,

System model

In this section, we gave a Meta-model of Compute-Independence (CIM) for HQESPNM firstly. For the system design, according to the CIM, a Model of Platform-Independence (PIM) for HQESPNM was given through approach of OOA&OOD [3][4]. In the PIM, we illustrated the relation between Nh and Np as well as the relation between Nq and Np .

System Architecture

The basic components of halal products formal producing system includes:

(1) Formal Management Information System (FMIS).

(2) Processing Standardization Information System (PSIS).

(3) Market Management Information System (MMIS).

(4) Scientific Food Management Information System.

(5) Animal Epidemic Diagnose Information System. (6) Quality Traceability Information System (QTIS). Halal Traceability Information System (HTIS) (8) Public Data Traceability Information System. (9) Traceability Data Bus based on Data Integrity Middleware. Among the components above:

(1),( 2) and (3) consists of the Np in HQESPNM, which is the major body of halal products formal producing system, representing Pre-processing, Processing and Postprocessing stage respectively.

(4) and ( 5) assist the normal running of Np . ( 4) is a non-independent component of the Formal Management Information System, on the contrary, ( 5) is an independent component based on artificial intelligence, which can be loaded or unloaded freely. ( 6) and ( 7) consists of the Nq and Nh respectively in HQESPNM, which are the kernel of halal products formal producing system. ( 8) is a trusted third-party component, which provide common qualification data to the Nq via exchange interface of (9). ( 9) is Traceability Data Bus based on Data Integrity Middleware, connecting the components mentioned above as a whole system, assurance the Np could be operated under the controlling of Nq .

CIM of system architecture can be described as Fig. 1.

Overview of HQESPNM by example

Based on the research above, we developed a set of software prototype named as Hqespnm1.0 to certificate the correctness of the HQESPNM. In this section, we presented an example to introduce the set of software prototype as Fig. 3.

Conclusion and future working

Address to Halal & Quality attributes assurance problem of formal producing system, the basic concept and notation of HQESPNM is given firstly, and the software model including architecture and design is presented secondly. Based on the model, this paper introduced an application example in electronic agriculture domain covering whole producing process including Pre-producing, Producing, Postproducing finally.

Results indicated that the HQESPNM separate the normal producing elements and Halal & Quality controlling elements into Petri Nets and Stochastic Petri Nets through Place expanding Petri Net [START_REF] Qi Fang-Min | A Modeling Method of Software Project Management Based on Petri Nets[END_REF] successfully. In future, the formal work of HQESPNM should be implemented to certificate its correctness.

Fig. 1 CIM of System Architecture 3 . 2

 132 Fig.1 CIM of System Architecture

F

  in HQESPNM

Fig. 3

 3 Fig.3 Hqespnm1.0 based on HQESPNM Hqespnm1.0 consists of Halal Traceability Information System (HTIS) and Quality Traceability Information System (QTIS), which show as upper part and Lower half of Fig.3 respectively.

  If t is enable under the marking M, then t can be fired. The marking Thus, M′ is reachable from M. The set of reachable markings from M is denoted as R(M).

										,					P	T	F	is called
	the spanning subnet of P1.
	Definition 2 Let M(p) be the number of tokens in place p. For	t 	T	,
	(1) t is enable under the marking M, denoted by	M	[ t	, 	iff	.  p 	t	:	M	(	p	)		; 1	;
	(2) ' M is obtained from M by firing t, denoted by	[ t M 	M	'	:
	The properties derived from execution of the Petri net are called dynamic
	properties or behavioral properties.
	A Petri net  	(	,	,	;	0	)

Halal & Quality Elements Extended SPN Model (HQESPNM)

  Based on the Stochastic Petri Nets and Place expanding Petri Net, this paper presented a Halal&Quality Elements Extended SPN Model (HQESPNM). Nq represent abstract of Quality-element relation, Np represent abstract of Animal Products Producing, F represent abstract of controlling from Nh and Nq to Np and reflection from Np to Nh and Nq .

		(	,	)					:																	,	(	.
	2.3 Definition 8  	(	, Nh	, Nq	, Np	F	)	is a HQESPNM, where:
	(1)	Nh 	(	P		,	T		,	F		;	M	Nh	)	is a Petri Nets.
							Nh		Nh					Nh				0
	(2)	Nq 	(	Nq P	,	Nq T	,	Nq F	;	M	0 Nq	)		is a Petri Nets.
	(3)	Np		(	Np P	,	Np T	,	Np F	;	M	0 Np	,	K	Np	,	Np W	,		Np	)	is a Stochastic Petri Nets.
	(4)	F		{ 	, p	t				t	,	p	| 	p		(	Nh P		Nq P	),	t		Np T	}	 t p,		means a Halal or
	Quality data flow/transition from	Nh or Nq to Np ; on the contrary,	 p t,		means
	a Halal or Quality data flow/transition from Np	Nh or Nq .
	For the application in the Introduction of this paper,	Nh represent abstract of
	Halal-element relation,

Acknowledgement

This paper is supported by National Key Technology R&D Program of China under Grant No.2007BAD33B03,Natural Science Foundation of NingXia Province under Grant No.NZ0955 and the Colleges Oriented Scientific Research Fund of NingXia Provincial Education Department of China under Grant No.2008JY009. Additionally, we should thank for the software prototype development work distributed by our colleagues and master candidate students: Ding HongSheng, Yang YongSheng, Shi Liang and Liu Yang.


Juan Pan
email: juan_pan@163.com

Na Zhang

Shan Yao

Jian Xu

Construction and Practice of Information Demonstration Area in Mentougou District of Beijing

Keywords: rural informatization, information demonstration area, 3S, information service platform, Eco-Agriculture

The rural informatization is one of the important foundation for the construction of the metropolis-modern agriculture, which Beijing government makes great effort to develop now. Based on current situation of rural informatization construction in Mentougou district of Beijing, this study established an information demonstration area in order to integrate the information from the local natural ecology, agricultural production, special products trading and government. We made use of the technology of 3S, database and network to achieve the digitalization and visualization of the rural information. The study helps to guide the agricultural production and agricultural products circulation and offers the effective decision support for the sustainable development of the demonstration area.

Introduction

With the balance development of modern rural and urban areas, Beijing strengthens the rural informatization construction. The rural information infrastructure in Mentougou district has made remarkable progress after years of effort. An integrated basic information service network has been established, which provides a strong guarantee for Mentougou informatization construction [START_REF] Shi | Reflections and Suggestions On Rural Informatization Construction in the Mountain Areas of Beijing (in Chinese)[END_REF]. 3S and Internet technology provide a new mode for the management of rural information, which realizes the management of spatial information that can't be carried out in the traditional one.

The Commission of Science and Technology of Mentougou district has established three websites successively-High-quality Goods Website, Chinese Walnut Website and Ecology Commercial City Website. However, the first two websites do not have the background system, and the third one needs to improve its trading function. Furthermore, these three websites provide some redundant function, and their network systems are instable. According to the current situation of informatization construction in Mentougou district, the study established information demonstration area in order to strengthen coordination and integration of rural information resources, and effectively promote the development of information technology in rural areas. We made use of 3S, database and network technology to manage and develop all kinds of rural information. Through the digitalization and visualization of the rural information, the study helps to guide the agricultural production and agricultural products circulation and offers the effective decision support for the sustainable development of the demonstration area.

2

The Overview of Study Area

Structure and Function of the System

According to the requirement of the eco-conservation and terrain features, the study established the information demonstration area in order to improve the competitiveness of agricultural products, optimize and upgrade the rural economic structure, and transform the pattern of economic growth. The construction of information demonstration area made full use of the advantages of GIS in data management, information visualization and spatial information analysis, integrated the information of natural ecology, agricultural production, special products trading and government, and established an eco-agriculture information service platform. Two towns, Wangping and Miaofenshan, are firstly selected as the experimental units.

Then the practice is extended to the whole district.

Natural Ecological Information Module

This module provides information display and query of meteorological, natural vegetation, hydrology, geology, soil type and so on. The meteorological information mainly involves temperature, relative humidity, precipitation and sunshine hours.

Agricultural Production Information Module

This module mainly records the information of agricultural resources to realize the network management of agricultural production process. The information includes farm fields, soil nutrient, soil fertility, varieties of agricultural products, planting area, tree age and its spatial distribution. The soil nutrient includes the organic matter, total nitrogen, available nitrogen, available phosphorus, available potassium and PH value. In addition, according to standardized production practice, this module records the information of water and fertilizer management , training and pruning , pest control, growth process of crop and so on. All of the above mentioned information can be displayed and queried with the field parcel as a unit.

Special Products Trading Module

Mentougou district produces abundantly special products, such as pear, walnut, cherry, almond and apricot. Some products, named as the tributes to the imperial palace, are famous over China, especially the roses in Xiangjiangou Village, Miaofengshan town enjoy sound reputation both in domestic and overseas due to big flowers, thick petal, dense color, fragrant gout and high oil content. Special products trading module realizes online trading and product tracing. Online trading mainly includes product information publication and recommendation, agricultural product credit guarantees, payment function, distribution process and information flow records. For the function of tracing back the product information, the product identification codes are affixed to the smallest package. With the unique identification code, the platform can query the detailed records of production management, products processing, logistics distribution information, and builds the quality assurance system from the origin of product to the market.

Government Affair Management Module

This module issues the related policies and regulations information, and manages the daily business of towns and villages. The module emphasizes on the statistics analysis of social and economic data to provide the basic economic evaluation. The data includes numbers of households, total population, per capital annual net income, per capital disposable income, annual wages income, household business income, annual property income, annual transfer income, total expenditure and others.

Implementing Scheme

As shown in Fig. 1, implementing scheme of the system is composed of data acquisition and processing, database construction and network platform construction.

Data Acquisition and Processing

The basic data and maps need to be collected and integrated. The data includes satellite image map, basic map and thematic map, statistical data on rural economy over years, and other agricultural data of meteorology and envirnment and etc.

Database Construction

Rural information resources mainly include natural resource information, ecological information, agricultural production management information, agricultural market information and government affair information. All the information are processed, formatted and saved in the information resource database, which can be easily saved, retrieved, transmitted, published and shared through modern information technology.

According to the local conditions, the information demonstration area constructs the spatial and attribute database, among which spatial information service is the basic database. The accuracy, capacity, coverage and update of spatial database not only affect the current construction of information demonstration area, but also have farreaching influence on the economy of the district and the scientific value of the study. Spatial database integrates the information of topographic, traffic network, administrative division, soil type, soil nutrient, land use status, field parcel distribution , temperature,rainfall and so on. Attribute database includes agricultural production information, product trading information, product tracing and management of administrative villages. All the information is connected with field parcel data.

Network Platform Construction

The study establishes Mentougou Eco-Agriculture information service platform, using .NET, SQL Server and SuperMap as development tools, C# as development language. The platform integrates four above-mentioned information management modules to realize the information query, analysis, decision-making, trading, trace back and others. The browser/server structure is applied to the system, and the client users can access the platform using a web browser. Mentougou geographical space data is showed as Fig. 2, which realizes management and visualization of data such as village boundary, road, water system, soil, vegetation, landform, farmland and soil using style, etc. The system can brings plane map as well as three-dimensional relief map, both of the ways of showing can realize the zooming in and zooming out of the map. In addition, relief map has flight function, which means the user can get access to related information of three-dimensional landform by user-defined route.

Function Actualization of System

The system provides two query methods: query map by attribute and query attribute by map. As shown in Fig. 3, based on the year, names of town and administrative village selected by the user, the system shows relevant positional information. When the user clicks on the map, the system will show information from the attribute database, such as area, numbers of households, agricultural population, income, climate, fertility of soil, etc.

Conclusion and Prospect

The study establishes the information demonstration area based on the technology of .NET, 3S and database to realize the integration of rural information resources. Through fully utilizing the advantages of GIS in map expression, spatial data management and map processing, the information service platform improves the visualization and convenient of management of rural information, advances the management efficiency of rural information.

Further study and discussion:

(1) To provide technical support for the planting structure adjustment, product variety update and agricultural division based on further study on the database of climate and agricultural resources.

(2) To establish the fertilizer recommendation system for green food according to the soil nutrient database of special products, and to provide scientific support for cultivation of high yield and quality with the study of the relation between soil nutrition status and product yield and quantity.

(3) To establish the remote sensing monitoring system to monitor diseases and insect pests of special products and provide real reference for decision-making.

(4) To build comprehensive evaluation model for ecological capacity maximizing the ecological, economic and social benefits in order to promote the virtuous circle of ecosystem, and provide decision support for sustainable development of the area.

Fig. 1 .

 1 Fig. 1. Implementing scheme of the system

Fig. 2 .

 2 Fig. 2. Visualization showing interface of Mentougou geographical space data

Fig. 3 .

 3 Fig. 3. Query result of administrative village

Acknowledgments

This study was funded by the Commission of Science and Technology of Mentougou district, and the project number is D0804090041000.