NDLI: Finding all longest common segments in protein structures efficiently

Content Provider	ACM Digital Library
Author	Ng, Yen Kaow Li, Shuai Cheng Yin, Linzhi Ono, Hirotaka
Copyright Year	2015
Description	Author Affiliation: Department of Computer Science, Faculty of Information and Communication Technology, Universiti Tunku Abdul Rahman, Kampar, Malaysia(Li, Shuai Cheng; Department of computer science, City University of Hong Kong, Hong Kong (Yin, Linzhi; Department of economic engineering, Faculty of Economics, Kyushu University, Fukuoka, Japan (Ono, Hirotaka); Ng, Yen Kaow))
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 = (a1; . . . ; an) and B = (b1; . . . ; bn) where ak, bk ∈ $R^{3},$ we are to find, among all the segments f = (ai; . . . ; aj) and g = (bi; . . . ; bj) 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 $\textit{f}$ and $\textit{g}$ is to be within a given $\textit{t}$ ∈ R; (2) $\textit{f}$ and $\textit{g}$ can be superposed such that for each k, i ≤ k ≤ j, \|\|ak - bk\|\| ≤ t for a given $\textit{t}$ ∈ R. We give an algorithm of O(n log n + nl) time complexity when the first requirement applies, where $\textit{l}$ is the maximum length of the segments fulfilling the criterion. We show an FPTAS which, for any ε ∈ R, finds a segment of length at least $\textit{l},$ but of RMSD up to (1 + $&epsilon)\textit{t},$ in O(n log n + n/ε) time. We propose an FPTAS which for any given ε ∈ R, finds all the segments $\textit{f}$ and $\textit{g}$ of the maximum length which can be superposed such that for each k, i ≤ k ≤ j, \|\|ak - bk\|\| ≤ (1 + &epsilon)t, thus fulfilling the second requirement approximately. The algorithm has a time complexity of O(n $log^{2}$ $n/ε^{5})$ when consecutive points in A are separated by the same distance (which is the case with protein structures). These worst-case runtime complexities are verified using C++ implementations of the algorithms, which we have made available at http://alcs.sourceforge.net/.
Ending Page	655
Page Count	12
Starting Page	644
File Format	PDF
ISSN	15455963
DOI	10.1109/TCBB.2014.2372782
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
Issue Number	3
Volume Number	12
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-05-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	PTAS Local/global alignment (LGA) Longest common structure RMSD
Content Type	Text
Resource Type	Article
Subject	Genetics Biotechnology Applied Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Finding All Longest Common Segments in Protein Structures Efficiently

Defining and Computing Optimum RMSD for Gapped and Weighted Multiple-Structure Alignment

TRIAL: A Tool for Finding Distant Structural Similarities

Defining and Computing Optimum RMSD for Gapped and Weighted Multiple-Structure Alignment

Optimizing a Widely Used Protein Structure Alignment Measure in Expected Polynomial Time

On Complexity of Protein Structure Alignment Problem under Distance Constraint

A Spectral Approach to Protein Structure Alignment

An adaptive hybrid algorithm for global network alignment

Global network alignment in the context of aging

Finding all longest common segments in protein structures efficiently

Similar Documents

Finding All Longest Common Segments in Protein Structures Efficiently

Defining and Computing Optimum RMSD for Gapped and Weighted Multiple-Structure Alignment

TRIAL: A Tool for Finding Distant Structural Similarities

Defining and Computing Optimum RMSD for Gapped and Weighted Multiple-Structure Alignment

Optimizing a Widely Used Protein Structure Alignment Measure in Expected Polynomial Time

On Complexity of Protein Structure Alignment Problem under Distance Constraint

A Spectral Approach to Protein Structure Alignment

An adaptive hybrid algorithm for global network alignment

Global network alignment in the context of aging

Finding all longest common segments in protein structures efficiently