Name
Abstract | ||
|---|---|---|
The Local/Global Alignment (Zemla, 2003), or LGA, is a popular method for the comparison of protein structures. One of the two components of LGA requires us to compute the longest common contiguous segments between two protein structures. That is, given two structures $A=(a_1, ldots , a_n)$ and $B=(b_1, ldots , b_n)$ where $a_k$ , $b_kin mathbb {R}^3$ , we are to find, among all the segments $f=(a_i,ldots ,a_j)$ and $g=(b_i,ldots ,b_j)$ that fulfill a certain criterion regarding their similarity, those of the maximum length. We consider the following criteria: (1) the root mean squared deviation (RMSD) between $f$ and $g$ is to be within a given $tin mathbb {R}$ ; (2) $f$ and $g$ can be superposed such that for each $k$ , $ile kle j$ , $Vert a_k-b_kVert le t$ for a given $tin mathbb {R}$ . We give an algorithm of $O(n;log; n+n{{boldsymbol l}})$ time complexity when the first requirement applies, where ${{boldsymbol l}}$ is the maximum length of the segments fulfilling the criterion. We show an FPTAS which, for any |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TCBB.2014.2372782 | Computational Biology and Bioinformatics, IEEE/ACM Transactions |
Keywords | Field | DocType |
lga,local/global alignment,local/global alignment (lga),ptas,rmsd,longest common structure,proteins,bioinformatics,approximation algorithms,time complexity,computational biology | Approximation algorithm,Combinatorics,Pairwise sequence alignment,Artificial intelligence,Root mean square,Bioinformatics,Time complexity,Mathematics,Machine learning,Protein structure | Journal |
Volume | Issue | ISSN |
12 | 3 | 1545-5963 |
Citations | PageRank | References |
1 | 0.40 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yen Kaow Ng | 1 | 73 | 9.46 |
| Linzhi Yin | 2 | 1 | 0.40 |
| Hirotaka Ono | 3 | 400 | 56.98 |
| Shuai Cheng Li | 4 | 184 | 30.25 |