Construction of orthogonal CC-sets

Abstract

In this paper we present a graph-theoretical method for computing the maximum orthogonal subset of a set of coiled-coil peptides. In chemistry, an orthogonal set of peptides is defined as a set of pairs of peptides, where the paired peptides interact only mutually and not with any other peptide from any other pair.The main method used is a reduction to the maximum independent set problem. Then we use a relatively well-known maximum independent set solving algorithm which turned out to be the best suited for our problem. We obtained an orthogonal set consisting of 29 peptides (homodimeric and heterodimeric) from initial 5-heptade set. If we allow only heterodimeric interactions we obtain an orthogonal set of 26 peptides.

References

M. Depolli, J. Konc, K. Rozman, R. Trobec, and D. Janezic. Exact parallel maximum clique algorithm for general and protein graphs. Journal of chemical information and modeling, 53(9):2217–2228, 2013.

H. Gradišar, S. Božič, T. Doles, D. Vengust, I. Hafner-Bratkovič, A. Mertelj, B. Webb, A. Šali, S. Klavžar, and R. Jerala. Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments. Nature chemical biology, 9(6):362–366, 2013.

V. Potapov, J. B. Kaplan, and A. E. Keating. Data-driven prediction and design of bzip coiled-coil interactions. PLoS Comput Biol, 11(2):1–28, 02 2015.

Authors

  • Andrej Brodnik University of Primorska
  • Vladan Jovičić École Normale Supérieure
  • Marko Palangetić University of Primorska
  • Daniel Silađi University of Primorska

DOI:

https://doi.org/10.31449/inf.v43i1.2693

Downloads

Additional Files

Published

03/01/2019

How to Cite

Brodnik, A., Jovičić, V., Palangetić, M., & Silađi, D. (2019). Construction of orthogonal CC-sets. Informatica, 43(1). https://doi.org/10.31449/inf.v43i1.2693

Issue

Vol. 43 No. 1 (2019)

Section

Middle-European Conference on Applied Theoretical Computer Science (MATCOS-16)

License

Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.

All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.

Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.