Biomedical subjects

Guohui Lin

Publications and source records attributed to Guohui Lin.

2 recordsLinked to original sources

PubMed2003

Protein threading by linear programming.

Protein three-dimensional structure prediction through threading approach has been extensively studied and various models and algorithms have been proposed. In order to further explore ways to improve accuracy and efficiency of the threading process, this paper investigates the effectiveness of a new method: protein threading via linear programming. Based on the contact map model of protein 3D structure, we formulate the protein threading problem as a large scale integer programming problem, then relax to a linear programming problem, and finally solve the integer program by a branch-and-bound method. The final solution is optimal with respect to energy functions incorporating pairwise interaction and allowing variable gaps. The algorithm has been implemented as software package RAPTOR--RApid Protein Threading predictOR. Experimental results for fold recognition show that RAPTOR significantly outperforms other programs at the fold similarity level. The RAPTOR webserver is at http://www.cs.uwaterloo.ca/-j3xu/RAPTOR_form.htm.

Algorithms↗

PubMed2002

A general edit distance between RNA structures.

Arc-annotated sequences are useful in representing the structural information of RNA sequences. In general, RNA secondary and tertiary structures can be represented as a set of nested arcs and a set of crossing arcs, respectively. Since RNA functions are largely determined by molecular confirmation and therefore secondary and tertiary structures, the comparison between RNA secondary and tertiary structures has received much attention recently. In this paper, we propose the notion of edit distance to measure the similarity between two RNA secondary and tertiary structures, by incorporating various edit operations performed on both bases and arcs (i.e., base-pairs). Several algorithms are presented to compute the edit distance between two RNA sequences with various arc structures and under various score schemes, either exactly or approximately, with provably good performance. Preliminary experimental tests confirm that our definition of edit distance and the computation model are among the most reasonable ones ever studied in the literature.

Algorithms↗