title: Parallel algorithms for finding a near-maximum independent set of a circle graph.
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.
authors.affiliation: Dept. of Electr. Eng. and Appl. Phys., Case Western Reserve Univ., Cleveland, OH.
authors.forename: Y
authors.initials: Y
authors.lastname: Takefuji
authors.forename: L L
authors.initials: LL
authors.lastname: Chen
authors.forename: K C
authors.initials: KC
authors.lastname: Lee
authors.forename: J
authors.initials: J
authors.lastname: Huffman