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

Volume

1

Issue

3

fYear

1990

fDate

9/1/1990 12:00:00 AM

Firstpage

263

Lastpage

267

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;

fLanguage

English

Journal_Title

Neural Networks, IEEE Transactions on

Publisher

ieee

ISSN

1045-9227

Type

jour

DOI

10.1109/72.80251

Filename

80251