Title :
Parallel algorithms for finding a near-maximum independent set of a circle graph
Author :
Takefuji, Yoshiyasu ; Chen, Li-Lin ; Lee, Kuo-Chun ; Huffman, John
Author_Institution :
Dept. of Electr. Eng. & Appl. Phys., Case Western Reserve Univ., Cleveland, OH, USA
fDate :
9/1/1990 12:00:00 AM
Abstract :
A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph of the number of possible base pairs), not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. The simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid, than previously proposed structures
Keywords :
graph theory; iterative methods; neural nets; parallel algorithms; set theory; RNA; base pairs; cardinality; circle graph; edges; iteration steps; near-maximum independent set; neural network array; parallel algorithm; potato spindle tuber viroid; ribonucleic acids; secondary structure prediction; stable structures; vertices; Backpropagation algorithms; Computational modeling; Concurrent computing; Neural networks; Organisms; Parallel algorithms; RNA; Sequences; Shape; Testing;
Journal_Title :
Neural Networks, IEEE Transactions on
