Abstract
Instances of the distance geometry can be represented by a simple weighted undirected graph G. Vertex orders on such graphs are discretization orders if they allow for the discretization of the K-dimensional search space of the distance geometry. A pseudo de Bruijn graph B associated to G is proposed in this paper, where vertices correspond to (K + 1)-cliques of G, and there is an arc from one vertex to another if, and only if, they admit an overlap, consisting of K vertices of G. This pseudo de Bruijn graph B can be exploited for constructing discretization orders for G for which the consecutivity assumption is satisfied. A new atomic order for protein backbones is presented, which is optimal in terms of length.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Almeida, F.C.L., Moraes, A.H., Gomes-Neto, F.: An Overview on Protein Structure Determination by NMR. Historical and Future Perspectives of the Use of Distance Geometry Methods. In: [19], pp. 377–412 (2013)
de Bruijn, N.G.: A Combinatorial Problem, Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758–764 (1946)
Canutescu, A.A., Shelenkov, A.A., Dunbrack Jr., R.L.: A Graph-Theory Algorithm for Rapid Protein Side-Chain Prediction. Protein Science 12, 2001–2014 (2003)
Cassioli, A., Günlük, O., Lavor, C., Liberti, L.: Discretization Vertex Orders in Distance Geometry. To appear in Discrete Applied Mathematics (2015)
Chikhi, R., Rizk, G.: Space-Efficient and Exact de Bruijn Graph Representation based on a Bloom Filter. Algorithms for Molecular Biology 8(22), 9 (2013)
Compeau, P.E.C., Pevzner, P.A., Tesler, G.: How to Apply de Bruijn Graphs to Genome Assembly. Nature Biotechnology 29, 987–991 (2011)
Costa, V., Mucherino, A., Lavor, C., Cassioli, A., Carvalho, L.M., Maculan, N.: Discretization Orders for Protein Side Chains. Journal of Global Optimization 60(2), 333–349 (2014)
Drezen, E., Rizk, G., Chikhi, R., Deltel, C., Lemaitre, C., Peterlongo, P., Lavenier, D.: GATB: Genome Assembly & Analysis Tool Box. To appear in Bioinformatics. Oxford Press (2014)
Ellis, T., Adie, T., Baldwin, G.S.: DNA Assembly for Synthetic Biology: from Parts to Pathways and Beyond. Integrative Biology 3, 109–118 (2011)
Kim, D.-S., Ryu, J.: Side-chain Prediction and Computational Protein Design Problems. Biodesign 2(1), 26–38 (2014)
Lavor, C., Lee, J., Lee-St. John, A., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization Orders for Distance Geometry Problems. Optimization Letters 6(4), 783–796 (2012)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The Discretizable Molecular Distance Geometry Problem. Computational Optimization and Applications 52, 115–146 (2012)
Lavor, C., Liberti, L., Mucherino, A.: The interval,Branch-and-Prune Algorithm for the Discretizable Molecular Distance Geometry Problem with Inexact Distances. Journal of Global Optimization 56(3), 855–871 (2013)
Liberti, L., Lavor, C., Maculan, N.: A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem. International Transactions in Operational Research 15, 1–17 (2008)
Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean Distance Geometry and Applications. SIAM Review 56(1), 3–69 (2014)
Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular Distance Geometry Methods: from Continuous to Discrete. International Transactions in Operational Research 18(1), 33–51 (2011)
Malliavin, T.E., Mucherino, A., Nilges, M.: Distance Geometry in Structural Biology: New Perspectives. In: [19], pp. 329–350 (2013)
Mucherino, A.: On the Identification of Discretization Orders for Distance Geometry with Intervals. In: Nielsen, F., Barbaresco, F. (eds.) GSI 2013. LNCS, vol. 8085, pp. 231–238. Springer, Heidelberg (2013)
Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.): Distance Geometry: Theory, Methods and Applications, 410 pages. Springer (2013)
Mucherino, A., Lavor, C., Malliavin, T., Liberti, L., Nilges, M., Maculan, N.: Influence of Pruning Devices on the Solution of Molecular Distance Geometry Problems. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 206–217. Springer, Heidelberg (2011)
Saxe, J.: Embeddability of Weighted Graphs in k-Space is Strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480–489 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Mucherino, A. (2015). A Pseudo de Bruijn Graph Representation for Discretization Orders for Distance Geometry. In: Ortuño, F., Rojas, I. (eds) Bioinformatics and Biomedical Engineering. IWBBIO 2015. Lecture Notes in Computer Science(), vol 9043. Springer, Cham. https://doi.org/10.1007/978-3-319-16483-0_50
Download citation
DOI: https://doi.org/10.1007/978-3-319-16483-0_50
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16482-3
Online ISBN: 978-3-319-16483-0
eBook Packages: Computer ScienceComputer Science (R0)