0
喜欢
0
书签
声明论文
Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment   
摘  要:   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.
发  表:   Algorithms in Bioinformatics  2005

论文统计图
共享有8个版本
 [展开全部版本] 

Bibtex
创新指数 
阅读指数 
重现指数 
论文点评
还没有人点评哦

Feedback
Feedback
Feedback
我想反馈:
排行榜