Abstract
We study a constrained bipartite matching problem where the input is a weighted bipartite graph G = (U, V,E), U is a set of vertices following a sequential order, V is another set of vertices partitioned into a collection of disjoint subsets, each following a sequential order, and E is a set of edges between U and V with non-negative weights. The objective is to find a matching in G with the maximum weight that satisfies the given sequential orders on both U and V, i.e., if u i+1 follows u i in U and if v j+1 follows v j in V, then u i is matched with v j if and only if u i+1 is matched with v j+1. The problem has recently been formulated as a crucial step in an algorithmic approach for interpreting NMR spectral data [15]. The interpretation of NMR spectral data is known as a key problem in protein structure determination via NMR spectroscopy. Unfortunately, the constrained bipartite matching problem is NP-hard [15]. We first propose a 2-approximation algorithm for the problem, which follows directly from the recent result of Bar-Noy et al. [2] on interval scheduling. However, our extensive experimental results on real NMR spectral data illustrate that the algorithm performs poorly in terms of recovering the target-matching (i.e. correct) edges. We then propose another approximation algorithm that tries to take advantage
Supported in part by the Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Sports and Culture of Japan, under Grant No. 12780241. Part of the work done while visiting at UC Riverside.
Supported in part by a UCR startup grant and NSF Grants CCR-9988353 and ITR-0085910.
Supported in part by NSERC grants RGPIN249633 and A008599, and Startup Grant REE-P5-01-02-Sci from the University of Alberta.
Supported by NSF Grant CCR-9988353.
Supported by the Office of Biological and Environmental Research, U.S. Department of Energy, under Contract DE-AC05-00OR22725, managed by UT-Battelle, LLC.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
International Human Genome Sequencing Consortium. Initial Sequencing and Analysis of the Human Genome. Nature, 409:860–921, 2001.
A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48:1069–1090, 2001.
R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27–46, 1985.
C. Bartels, P. Güntert, M. Billeter, and K. Wüthrich. GARANT-A general algorithm for resonance assignment of multidimensional nuclear magnetic resonance spectra. Journal of Computational Chemistry, 18:139–149, 1996.
T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. The MIT Press, 1990.
P. Güntert, M. Salzmann, D. Braun, and K. Wüthrich. Sequence-specific NMR assignment of proteins by global fragment mapping with the program mapper. Journal of Biomolecular NMR, 18:129–137, 2000.
K. Huang, M. Andrec, S. Heald, P. Blake, and J.H. Prestegard. Performance of a neural-network-based determination of amino acid class and secondary structure from 1H-15N NMR data. Journal of Biomolecular NMR, 10:45–52, 1997.
V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37:27–35, 1991.
National Institute of General Medical Sciences. Pilot projects for the protein structure initiative (structural genomics). June 1999. Web page at http://www.nih.gov/grants/guide/rfa-files/RFA-GM-99-009.html.
C.H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425–440, 1991.
C. A. Rohl and D. Baker. De novo determination of protein backbone structure from residual dipolar couplings using Rosetta. Journal of The American Chemical Society, 124:2723–2729, 2002.
F. Tian, H. Valafar, and J. H. Prestegard. A dipolar coupling based strategy for simultaneous resonance assignment and structure determination of protein backbones. Journal of The American Chemical Society, 123:11791–11796, 2001.
University of Wisconsin. BioMagResBank. http://www.bmrb.wisc.edu 2001.
J. Xu, S.K. Straus, B.C. Sanctuary, and L. Trimble. Use of fuzzy mathematics for complete automated assignment of peptide 1H 2D NMR spectra. Journal of Magnetic Resonance, 103:53–58, 1994.
Y. Xu, D. Xu, D. Kim, V. Olman, J. Razumovskaya, and T. Jiang. Automated assignment of backbone NMR peaks using constrained bipartite matching. IEEE Computing in Science & Engineering, 4:50–62, 2002.
D.E. Zimmerman, C.A. Kulikowski, Y. Huang, W.F.M. Tashiro, S. Shimotakahara, C. Chien, R. Powers, and G.T. Montelione. Automated analysis of protein NMR assignments using methods from artificial intelligence. Journal of Molecular Biology, 269:592–610, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhi-Zhong, C., Jiang, T., Lin, G., Wen, J., Xu, D., Xu, Y. (2002). Improved Approximation Algorithms for NMR Spectral Peak Assignment. In: Guigó, R., Gusfield, D. (eds) Algorithms in Bioinformatics. WABI 2002. Lecture Notes in Computer Science, vol 2452. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45784-4_7
Download citation
DOI: https://doi.org/10.1007/3-540-45784-4_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44211-0
Online ISBN: 978-3-540-45784-8
eBook Packages: Springer Book Archive