(68) Experimental Sequence Analysis System

	Machine:     PIM
	Environment: PIMOS
	Language:    KL1
	Source Code: 200 KB
	Documents:   Manual (English/Japanese)

Overview

Extracts common patterns(motifs) of amino acid sequences in some protein categories.

Characteristics

Motif extraction is one of the important problems in genetic information processing. Motifs are common patterns of amino acid sequences in the same protein category, which are conserved in the evolution process and characterize the function/structure of proteins. The system extracts motifs using the MDL principle and genetic algorithms.

Function

As a criterion for motif evaluation, the minimum description length(MDL) principle was adopted. The MDL principle selects a motif with the shortest description length ( = Complexity of motif + Classification error rate). It enables us to compare a simple motif with exceptions and a complex motif without exceptions.

As a motif search method, genetic algorithms (GA) were adopted to deal with enormous search space. GA realizes probabilistic search by applying genetic operations to a population of motif candidates represented by binary strings. The genetic operations consist of crossover, mutation and selection. The MDL principle plays an essential role in selection.

Three kinds of parallelism can be exploited in the system;trial, divide-and-conquer and data parallelism. They enable us to utilize the Parallel Inference Machine (PIM) effectively.

Bibliography

Konagaya, Stochastic Motifs, Genome Informatics Workshop II, 1991. (in Japanese)
Konagaya, et al., The MDL Principle and Genetic Information Processing, Proceedings of JSAI, 1991. (in Japanese)
Konagaya, et al., Stochastic Decision Predicate:A Scheme to Represent Motifs, AAAI Workshop, 1991.
Koyanagi el al., Protein Motif Extraction using Multi-PSI, Genome Informatics Workshop II, 1991. (in Japanese)
Yamanishi, et al., Learning Stochastic Motifs from Genetic Sequences, Machine Learning Workshop, 1991.

FTP

Experimental Sequence Analysis System [169K]

www-admin@icot.or.jp