Abstract
We study the additive errors in solutions to systems Ax = b of linear equations where vector b is corrupted, with a focus on systems where A is a 0,1-matrix with very sparse rows. We give a worst-case error bound in terms of an auxiliary LP, as well as graph-theoretic characterizations of the optimum of this error bound in the case of two variables per row. The LP solution indicates which measurements should be combined to minimize the additive error of any chosen variable. The results are applied to the problem of inferring the amounts of proteins in a mixture, given inaccurate measurements of the amounts of peptides after enzymatic digestion. Results on simulated data (but from real proteins split by trypsin) suggest that the errors of most variables blow up by very small factors only.
This is a preview of subscription content, log in via an institution to check access.
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
Arioli, M., Demmel, J.W., Duff, I.S.: Solving Sparse Linear Systems with Sparse Backward Error. SIAM J. Matrix Analysis and Appl. 10, 165–190 (1989)
Bantscheff, M., Schirle, M., Sweetman, G., Rick, J., Kuster, B.: Quantitative Mass Spectrometry in Proteomics: A Critical Review. Anal. Bioanal. Chem. 389, 1017–1031 (2007)
Boehm, A.M., Pütz, S., Altenhöfer, D., Sickmann, A., Falk, M.: Precise Protein Quantification Based on Peptide Quantification Using iTRAQ. BMC Bioinformatics 8, 214 (2007)
Chandrasekaran, S., Ipsen, I.C.F.: On the Sensitivity of Solution Components in Linear Systems of Equations. SIAM J. Matrix Analysis and Appl. 16, 93–112 (1995)
Damaschke, P.: Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 94–105. Springer, Heidelberg (2012)
Dost, B., Bafna, V., Bandeira, N., Li, X., Shen, Z., Briggs, S.: Shared Peptides in Mass Spectrometry Based Protein Quantification. In: Batzoglou, S. (ed.) RECOMB 2009. LNCS, vol. 5541, pp. 356–371. Springer, Heidelberg (2009)
Feige, U., Reichman, D.: On the Hardness of Approximating Max-Satisfy. Inf. Proc. Lett. 97, 31–35 (2006)
Fritzilas, E., Milanic, M., Rahmann, S., Rios-Solis, Y.A.: Structural Identifiability in Low-Rank Matrix Factorization. Algorithmica 53, 313–332 (2010)
Gerber, S.A., Rush, J., Stemman, O., Kirschner, M.W., Gygi, S.P.: Absolute Quantification of Proteins and Phosphoproteins from Cell Lysates by Tandem MS. Proc. Nat. Academy of Sc. USA 100, 6940–6945 (2003)
Giannopoulos, P., Knauer, C., Rote, G.: The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 198–209. Springer, Heidelberg (2009)
Nesvizhskii, A.I., Aebersold, R.: Interpretation of Shotgun Proteomic Data: The Protein Inference Problem. Mol. Cellular Proteomics 4, 1419–1440 (2005)
Yang, X., Dai, H., He, Q.: Condition Numbers and Backward Perturbation Bound for Linear Matrix Equations. Num. Lin. Algebra with Appl. 18, 155–165 (2011)
Zhang, B., Chambers, M.C., Tabb, D.L.: Proteomic Parsimony through Bipartite Graph Analysis Improves Accuracy and Transparency. J. Proteome Res. 6, 3549–3557 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damaschke, P., Molokov, L. (2012). Error Propagation in Sparse Linear Systems with Peptide-Protein Incidence Matrices. In: Bleris, L., Măndoiu, I., Schwartz, R., Wang, J. (eds) Bioinformatics Research and Applications. ISBRA 2012. Lecture Notes in Computer Science(), vol 7292. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30191-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-30191-9_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30190-2
Online ISBN: 978-3-642-30191-9
eBook Packages: Computer ScienceComputer Science (R0)