RIBRA - An error-tolerant algorithm for the NMR backbone assignment problem

Kun Pin Wu, Jia Ming Chang, Jun Bo Chen, Chi Fon Chang, Wen Jin Wu, Tai Huang Huang, Ting Yi Sung, Wen Lian Hsu

Research output: Contribution to journalArticle

19 Citations (Scopus)

Abstract

We develop an iterative relaxation algorithm called RIBRA for NMR protein backbone assignment. RIBRA applies nearest neighbor and weighted maximum independent set algorithms to solve the problem. To deal with noisy NMR spectral data, RIBRA is executed in an iterative fashion based on the quality of spectral peaks. We first produce spin system pairs using the spectral data without missing peaks, then the data group with one missing peak, and finally, the data group with two missing peaks. We test RIBRA on two real NMR datasets, hbSBD and hbLBD, and perfect BMRB data (with 902 proteins) and four synthetic BMRB data which simulate four kinds of errors. The accuracy of RIBRA on hbSBD and hbLBD are 91.4% and 83.6%, respectively. The average accuracy of RIBRA on perfect BMRB datasets is 98.28%, and 98.28%, 95.61%, 98.16%, and 96.28% on four kinds of synthetic datasets, respectively.

Original languageEnglish
Pages (from-to)229-244
Number of pages16
JournalJournal of Computational Biology
Volume13
Issue number2
DOIs
Publication statusPublished - 2006 Mar 1

Fingerprint

Assignment Problem
Backbone
Nuclear magnetic resonance
Proteins
Protein
Maximum Independent Set
Spin Systems
Synthetic Data
Nearest Neighbor
Assignment
Datasets

Keywords

  • Iterative relaxation algorithm
  • NMR resonance assignment
  • Nearest neighbor
  • Weighted maximum independent set

ASJC Scopus subject areas

  • Modelling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this

RIBRA - An error-tolerant algorithm for the NMR backbone assignment problem. / Wu, Kun Pin; Chang, Jia Ming; Chen, Jun Bo; Chang, Chi Fon; Wu, Wen Jin; Huang, Tai Huang; Sung, Ting Yi; Hsu, Wen Lian.

In: Journal of Computational Biology, Vol. 13, No. 2, 01.03.2006, p. 229-244.

Research output: Contribution to journalArticle

Wu, KP, Chang, JM, Chen, JB, Chang, CF, Wu, WJ, Huang, TH, Sung, TY & Hsu, WL 2006, 'RIBRA - An error-tolerant algorithm for the NMR backbone assignment problem', Journal of Computational Biology, vol. 13, no. 2, pp. 229-244. https://doi.org/10.1089/cmb.2006.13.229
Wu, Kun Pin ; Chang, Jia Ming ; Chen, Jun Bo ; Chang, Chi Fon ; Wu, Wen Jin ; Huang, Tai Huang ; Sung, Ting Yi ; Hsu, Wen Lian. / RIBRA - An error-tolerant algorithm for the NMR backbone assignment problem. In: Journal of Computational Biology. 2006 ; Vol. 13, No. 2. pp. 229-244.
@article{d618e2dc9276485c9ce9e472061c50d4,
title = "RIBRA - An error-tolerant algorithm for the NMR backbone assignment problem",
abstract = "We develop an iterative relaxation algorithm called RIBRA for NMR protein backbone assignment. RIBRA applies nearest neighbor and weighted maximum independent set algorithms to solve the problem. To deal with noisy NMR spectral data, RIBRA is executed in an iterative fashion based on the quality of spectral peaks. We first produce spin system pairs using the spectral data without missing peaks, then the data group with one missing peak, and finally, the data group with two missing peaks. We test RIBRA on two real NMR datasets, hbSBD and hbLBD, and perfect BMRB data (with 902 proteins) and four synthetic BMRB data which simulate four kinds of errors. The accuracy of RIBRA on hbSBD and hbLBD are 91.4{\%} and 83.6{\%}, respectively. The average accuracy of RIBRA on perfect BMRB datasets is 98.28{\%}, and 98.28{\%}, 95.61{\%}, 98.16{\%}, and 96.28{\%} on four kinds of synthetic datasets, respectively.",
keywords = "Iterative relaxation algorithm, NMR resonance assignment, Nearest neighbor, Weighted maximum independent set",
author = "Wu, {Kun Pin} and Chang, {Jia Ming} and Chen, {Jun Bo} and Chang, {Chi Fon} and Wu, {Wen Jin} and Huang, {Tai Huang} and Sung, {Ting Yi} and Hsu, {Wen Lian}",
year = "2006",
month = "3",
day = "1",
doi = "10.1089/cmb.2006.13.229",
language = "English",
volume = "13",
pages = "229--244",
journal = "Journal of Computational Biology",
issn = "1066-5277",
publisher = "Mary Ann Liebert Inc.",
number = "2",

}

TY - JOUR

T1 - RIBRA - An error-tolerant algorithm for the NMR backbone assignment problem

AU - Wu, Kun Pin

AU - Chang, Jia Ming

AU - Chen, Jun Bo

AU - Chang, Chi Fon

AU - Wu, Wen Jin

AU - Huang, Tai Huang

AU - Sung, Ting Yi

AU - Hsu, Wen Lian

PY - 2006/3/1

Y1 - 2006/3/1

N2 - We develop an iterative relaxation algorithm called RIBRA for NMR protein backbone assignment. RIBRA applies nearest neighbor and weighted maximum independent set algorithms to solve the problem. To deal with noisy NMR spectral data, RIBRA is executed in an iterative fashion based on the quality of spectral peaks. We first produce spin system pairs using the spectral data without missing peaks, then the data group with one missing peak, and finally, the data group with two missing peaks. We test RIBRA on two real NMR datasets, hbSBD and hbLBD, and perfect BMRB data (with 902 proteins) and four synthetic BMRB data which simulate four kinds of errors. The accuracy of RIBRA on hbSBD and hbLBD are 91.4% and 83.6%, respectively. The average accuracy of RIBRA on perfect BMRB datasets is 98.28%, and 98.28%, 95.61%, 98.16%, and 96.28% on four kinds of synthetic datasets, respectively.

AB - We develop an iterative relaxation algorithm called RIBRA for NMR protein backbone assignment. RIBRA applies nearest neighbor and weighted maximum independent set algorithms to solve the problem. To deal with noisy NMR spectral data, RIBRA is executed in an iterative fashion based on the quality of spectral peaks. We first produce spin system pairs using the spectral data without missing peaks, then the data group with one missing peak, and finally, the data group with two missing peaks. We test RIBRA on two real NMR datasets, hbSBD and hbLBD, and perfect BMRB data (with 902 proteins) and four synthetic BMRB data which simulate four kinds of errors. The accuracy of RIBRA on hbSBD and hbLBD are 91.4% and 83.6%, respectively. The average accuracy of RIBRA on perfect BMRB datasets is 98.28%, and 98.28%, 95.61%, 98.16%, and 96.28% on four kinds of synthetic datasets, respectively.

KW - Iterative relaxation algorithm

KW - NMR resonance assignment

KW - Nearest neighbor

KW - Weighted maximum independent set

UR - http://www.scopus.com/inward/record.url?scp=33645959198&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33645959198&partnerID=8YFLogxK

U2 - 10.1089/cmb.2006.13.229

DO - 10.1089/cmb.2006.13.229

M3 - Article

C2 - 16597237

AN - SCOPUS:33645959198

VL - 13

SP - 229

EP - 244

JO - Journal of Computational Biology

JF - Journal of Computational Biology

SN - 1066-5277

IS - 2

ER -