Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment
A PHP Error was encountered
Message: Undefined index: id
Line Number: 218
Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and con- sequently is computationally intractable. It is difficult to cope with the ineffi- ciency without compromising alignment accuracy, especially for structure search in genomes or large databases. Thispaperintroducesanovelmethodandaparameterizedalgorithmforstructure- sequencealignment.Boththestructureand thesequencearerepresentedasgraphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(ktN2) for the structure of N residues and its tree decomposition of width t. The parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.