{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:27:22Z","timestamp":1775068042840,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Projekt DEAL"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Conformational transitions are implicated in the biological function of many proteins. Structural changes in proteins can be described approximately as the relative movement of rigid domains against each other. Despite previous efforts, there is a need to develop new domain segmentation algorithms that are capable of analysing the entire structure database efficiently and do not require the choice of protein-dependent tuning parameters such as the number of rigid domains.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We develop a graph-based method for detecting rigid domains in proteins. Structural information from multiple conformational states is represented by a graph whose nodes correspond to amino acids. Graph clustering algorithms allow us to reduce the graph and run the Viterbi algorithm on the associated line graph to obtain a segmentation of the input structures into rigid domains. In contrast to many alternative methods, our approach does not require knowledge about the number of rigid domains. Moreover, we identified default values for the algorithmic parameters that are suitable for a large number of conformational ensembles. We test our algorithm on examples from the DynDom database and illustrate our method on various challenging systems whose structural transitions have been studied extensively.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>The results strongly suggest that our graph-based algorithm forms a novel framework to characterize structural transitions in proteins via detecting their rigid domains. The web server is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/azifi.tz.agrar.uni-goettingen.de\/webservice\/\">http:\/\/azifi.tz.agrar.uni-goettingen.de\/webservice\/<\/jats:ext-link>.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-021-03966-3","type":"journal-article","created":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T18:00:14Z","timestamp":1613152814000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A graph-based algorithm for detecting rigid domains in protein structures"],"prefix":"10.1186","volume":"22","author":[{"given":"Truong Khanh Linh","family":"Dang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thach","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Habeck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehmet","family":"G\u00fcltas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Waack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,12]]},"reference":[{"key":"3966_CR1","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1038\/nature06522","volume":"450","author":"K Henzler-Wildman","year":"2007","unstructured":"Henzler-Wildman K, Kern D. Dynamic personalities of proteins. Nature. 2007;450:964\u201372.","journal-title":"Nature"},{"issue":"22","key":"3966_CR2","doi-asserted-by":"publisher","first-page":"6739","DOI":"10.1021\/bi00188a001","volume":"33","author":"M Gerstein","year":"1994","unstructured":"Gerstein M, Lesk AM, Chothia C. Structural mechanisms for domain movements in proteins. Biochemistry. 1994;33(22):6739\u201349.","journal-title":"Biochemistry"},{"issue":"2","key":"3966_CR3","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1002\/(SICI)1097-0134(19980201)30:2<144::AID-PROT4>3.0.CO;2-N","volume":"30","author":"S Hayward","year":"1998","unstructured":"Hayward S, Berendsen HJ. Systematic analysis of domain motions in proteins from conformational change: new results on citrate synthase and t 4 lysozyme. Proteins Struct Funct Genet. 1998;30(2):144\u201354.","journal-title":"Proteins Struct Funct Genet"},{"issue":"1","key":"3966_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1097-0134(199709)29:1<1::AID-PROT1>3.0.CO;2-J","volume":"29","author":"W Wriggers","year":"1997","unstructured":"Wriggers W, Schulten K. Protein domain movements: detection of rigid domains and visualization of hinges in comparisons of atomic coordinates. Proteins Struct Funct Genet. 1997;29(1):1\u201314.","journal-title":"Proteins Struct Funct Genet"},{"issue":"2","key":"3966_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/prot.22544","volume":"78","author":"A Abyzov","year":"2010","unstructured":"Abyzov A, Bjornson R, Felipe M, Gerstein M. Rigidfinder: a fast and sensitive method to detect rigid blocks in large macromolecular complexes. Proteins Struct Funct Bioinform. 2010;78(2):309\u201324.","journal-title":"Proteins Struct Funct Bioinform"},{"issue":"8","key":"3966_CR6","doi-asserted-by":"publisher","first-page":"1516","DOI":"10.1016\/j.str.2015.05.022","volume":"23","author":"L Ponzoni","year":"2015","unstructured":"Ponzoni L, Polles G, Carnevale V, Micheletti C. Spectrus: a dimensionality reduction approach for identifying dynamical domains in protein complexes from limited structural datasets. Structure. 2015;23(8):1516\u201325.","journal-title":"Structure"},{"issue":"19","key":"3966_CR7","doi-asserted-by":"publisher","first-page":"2184","DOI":"10.1093\/bioinformatics\/btn396","volume":"24","author":"M Hirsch","year":"2008","unstructured":"Hirsch M, Habeck M. Mixture models for protein structure ensembles. Bioinformatics. 2008;24(19):2184\u201392.","journal-title":"Bioinformatics"},{"issue":"17","key":"3966_CR8","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1093\/bioinformatics\/btw442","volume":"32","author":"T Nguyen","year":"2016","unstructured":"Nguyen T, Habeck M. A probabilistic model for detecting rigid domains in protein structures. Bioinformatics. 2016;32(17):710\u20137.","journal-title":"Bioinformatics"},{"issue":"4","key":"3966_CR9","doi-asserted-by":"publisher","first-page":"1219","DOI":"10.1002\/prot.21613","volume":"70","author":"U Emekli","year":"2008","unstructured":"Emekli U, Schneidman-Duhovny D, Wolfson HJ, Nussinov R, Haliloglu T. Hingeprot: automated prediction of hinges in protein structures. Proteins Struct Funct Bioinform. 2008;70(4):1219\u201327.","journal-title":"Proteins Struct Funct Bioinform"},{"issue":"3","key":"3966_CR10","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1002\/(SICI)1097-0134(19981115)33:3<417::AID-PROT10>3.0.CO;2-8","volume":"33","author":"K Hinsen","year":"1998","unstructured":"Hinsen K. Analysis of domain motions by approximate normal mode calculations. Proteins Struct Funct Bioinform. 1998;33(3):417\u201329.","journal-title":"Proteins Struct Funct Bioinform"},{"issue":"1","key":"3966_CR11","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1186\/1471-2105-8-215","volume":"8","author":"SC Flores","year":"2007","unstructured":"Flores SC, Gerstein MB. Flexoracle: predicting flexible hinges by identification of stable domains. BMC Bioinform. 2007;8(1):215.","journal-title":"BMC Bioinform"},{"key":"3966_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0969-2126(96)00018-4","volume":"4","author":"CW Mueller","year":"1996","unstructured":"Mueller CW, Schlauderer GJ, Reinstein J, Schulz GE. Adenylate kinase motions during catalysis: an energetic counterweight balancing substrate binding. Structure. 1996;4:147\u201356.","journal-title":"Structure"},{"issue":"1","key":"3966_CR13","doi-asserted-by":"publisher","first-page":"016114","DOI":"10.1103\/PhysRevE.84.016114","volume":"84","author":"VA Traag","year":"2011","unstructured":"Traag VA, Van Dooren P, Nesterov Y. Narrow scope for resolution-limit-free community detection. Phys Rev E. 2011;84(1):016114. https:\/\/doi.org\/10.1103\/PhysRevE.84.016114.","journal-title":"Phys Rev E"},{"key":"3966_CR14","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1186\/1471-2105-15-277","volume":"15","author":"Z Dong","year":"2014","unstructured":"Dong Z, Wang K, Dang TKL, G\u00fcltas M, Welter M, Wierschin T, Stanke M, Waack S. Crf-based models of protein surfaces improve protein-protein interaction site predictions. BMC Bioinform. 2014;15:277. https:\/\/doi.org\/10.1186\/1471-2105-15-277.","journal-title":"BMC Bioinform"},{"key":"3966_CR15","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1016\/j.jmb.2006.11.085","volume":"366","author":"PC Whitford","year":"2007","unstructured":"Whitford PC, Miyashita O, Levy Y, Onuchic JN. Conformational transitions of adenylate kinase: switching by cracking. J Mol Biol. 2007;366:1661\u201371.","journal-title":"J Mol Biol"},{"key":"3966_CR16","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1002\/prot.25490","volume":"86","author":"M Habeck","year":"2018","unstructured":"Habeck M, Nguyen T. A probabilistic network model for structural transitions in biomolecules. Proteins. 2018;86:634\u201343. https:\/\/doi.org\/10.1002\/prot.25490.","journal-title":"Proteins"},{"issue":"10","key":"3966_CR17","doi-asserted-by":"publisher","first-page":"1290","DOI":"10.1093\/bioinformatics\/btg137","volume":"19","author":"RA Lee","year":"2003","unstructured":"Lee RA, Razaz M, Hayward S. The DynDom database of protein domain motions. Bioinformatics. 2003;19(10):1290\u20131.","journal-title":"Bioinformatics"},{"issue":"51","key":"3966_CR18","doi-asserted-by":"publisher","first-page":"14845","DOI":"10.1021\/bi701848w","volume":"46","author":"K Lim","year":"2007","unstructured":"Lim K, Read RJ, Chen CCH, Tempczyk A, Wei M, Ye D, Wu C, Dunaway-Mariano D, Herzberg O. Swiveling domain mechanism in pyruvate phosphate dikinase. Biochemistry. 2007;46(51):14845\u201353. https:\/\/doi.org\/10.1021\/bi701848w.","journal-title":"Biochemistry"},{"issue":"40","key":"3966_CR19","doi-asserted-by":"publisher","first-page":"12709","DOI":"10.1021\/bi0486987","volume":"43","author":"K Theis","year":"2004","unstructured":"Theis K, Gong P, Martin CT. Topological and conformational analysis of the initiation and elongation complex of T7 RNA polymerase suggests a new twist. Biochemistry. 2004;43(40):12709\u201315. https:\/\/doi.org\/10.1021\/bi0486987.","journal-title":"Biochemistry"},{"issue":"2","key":"3966_CR20","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1038\/nsb0296-170","volume":"3","author":"DC Boisvert","year":"1996","unstructured":"Boisvert DC, Wang J, Otwinowski Z, Norwich AL, Sigler PB. The 2.4 \u00e5 crystal structure of the bacterial chaperonin GroEL complexed with atpgs. Nat Struct Biol. 1996;3(2):170\u20137. https:\/\/doi.org\/10.1038\/nsb0296-170.","journal-title":"Nat Struct Biol"},{"issue":"1","key":"3966_CR21","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1172\/JCI103055","volume":"34","author":"A Karmen","year":"1955","unstructured":"Karmen A, Wroblewski F, Ladue JS. Transaminase activity in human blood. J Clin Investig. 1955;34(1):126\u201331. https:\/\/doi.org\/10.1172\/JCI103055.","journal-title":"J Clin Investig"},{"issue":"4986","key":"3966_CR22","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1038\/206757a0","volume":"206","author":"CCF Blake","year":"1965","unstructured":"Blake CCF, Koenig DF, Mair GA, North ACT, Phillips DC, Sarma VR. Structure of hen egg-white lysozyme: a three-dimensional fourier synthesis at 2 \u00e5 resolution. Nature. 1965;206(4986):757\u201361. https:\/\/doi.org\/10.1038\/206757a0.","journal-title":"Nature"},{"issue":"6","key":"3966_CR23","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1016\/j.immuni.2017.05.002","volume":"46","author":"Y Zheng","year":"2017","unstructured":"Zheng Y, Han GW, Abagyan R, Wu B, Stevens RC, Cherezov V, Kufareva I, Handel TM. Structure of CC chemokine receptor 5 with a potent chemokine antagonist reveals mechanisms of chemokine recognition and molecular mimicry by HIV. Immunity. 2017;46(6):1005\u201310175. https:\/\/doi.org\/10.1016\/j.immuni.2017.05.002.","journal-title":"Immunity"},{"issue":"1","key":"3966_CR24","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1038\/msb.2011.75","volume":"7","author":"F Sievers","year":"2011","unstructured":"Sievers F, Wilm A, Dineen D, Gibson TJ, Karplus K, Li W, Lopez R, McWilliam H, Remmert M, S\u00f6ding J, Thompson JD, Higgins DG. Fast, scalable generation of high-quality protein multiple sequence alignments using clustal omega. Mol Syst Biol. 2011;7(1):539. https:\/\/doi.org\/10.1038\/msb.2011.75.","journal-title":"Mol Syst Biol"},{"issue":"1","key":"3966_CR25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/pro.3290","volume":"27","author":"F Sievers","year":"2017","unstructured":"Sievers F, Higgins DG. Clustal omega for making accurate alignments of many protein sequences. Protein Sci. 2017;27(1):135\u201345. https:\/\/doi.org\/10.1002\/pro.3290.","journal-title":"Protein Sci"},{"issue":"1","key":"3966_CR26","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/s1093-3263(00)00138-8","volume":"19","author":"AK Dunker","year":"2001","unstructured":"Dunker AK, Lawson JD, Brown CJ, Williams RM, Romero P, Oh JS, Oldfield CJ, Campen AM, Ratliff CM, Hipps KW, Ausio J, Nissen MS, Reeves R, Kang C, Kissinger CR, Bailey RW, Griswold MD, Chiu W, Garner EC, Obradovic Z. Intrinsically disordered protein. J Mol Graph Model. 2001;19(1):26\u201359. https:\/\/doi.org\/10.1016\/s1093-3263(00)00138-8.","journal-title":"J Mol Graph Model"},{"issue":"7792","key":"3966_CR27","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1038\/s41586-019-1923-7","volume":"577","author":"AW Senior","year":"2020","unstructured":"Senior AW, Evans R, Jumper J, Kirkpatrick J, Sifre L, Green T, Qin C, \u017d\u00eddek A, Nelson AWR, Bridgland A, Penedones H, Petersen S, Simonyan K, Crossan S, Kohli P, Jones DT, Silver D, Kavukcuoglu K, Hassabis D. Improved protein structure prediction using potentials from deep learning. Nature. 2020;577(7792):706\u201310. https:\/\/doi.org\/10.1038\/s41586-019-1923-7.","journal-title":"Nature"},{"issue":"3","key":"3966_CR28","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1002\/(SICI)1097-0134(199703)27:3<425::AID-PROT10>3.0.CO;2-N","volume":"27","author":"S Hayward","year":"1997","unstructured":"Hayward S, Kitao A, Berendsen HJC. Model-free methods of analyzing domain motions in proteins from simulation: a comparison of normal mode analysis and molecular dynamics simulation of lysozyme. Proteins Struct Funct Bioinform. 1997;27(3):425\u201337. https:\/\/doi.org\/10.1002\/(SICI)1097-0134(199703)27:3<425::AID-PROT10>3.0.CO;2-N.","journal-title":"Proteins Struct Funct Bioinform"},{"issue":"1","key":"3966_CR29","doi-asserted-by":"publisher","first-page":"2838","DOI":"10.1038\/s41598-017-01498-6","volume":"7","author":"J Salamanca Viloria","year":"2017","unstructured":"Salamanca Viloria J, Allega MF, Lambrughi M, Papaleo E. An optimal distance cutoff for contact-based protein structure networks using side-chain centers of mass. Sci Rep. 2017;7(1):2838. https:\/\/doi.org\/10.1038\/s41598-017-01498-6.","journal-title":"Sci Rep"},{"issue":"3","key":"3966_CR30","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/s1359-0278(97)00024-2","volume":"2","author":"I Bahar","year":"1997","unstructured":"Bahar I, Atilgan AR, Erman B. Direct evaluation of thermal fluctuations in proteins using a single-parameter harmonic potential. Fold Des. 1997;2(3):173\u201381. https:\/\/doi.org\/10.1016\/s1359-0278(97)00024-2.","journal-title":"Fold Des"},{"key":"3966_CR31","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1107\/S0567739476001873","volume":"32","author":"W Kabsch","year":"1976","unstructured":"Kabsch W. A solution for the best rotation to relate two sets of vectors. Acta Crystallogr Sect A. 1976;32:922\u20133. https:\/\/doi.org\/10.1107\/S0567739476001873.","journal-title":"Acta Crystallogr Sect A"},{"issue":"10","key":"3966_CR32","doi-asserted-by":"publisher","first-page":"10008","DOI":"10.1088\/1742-5468\/2008\/10\/p10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. J Stat Mech Theory Exp. 2008;2008(10):10008. https:\/\/doi.org\/10.1088\/1742-5468\/2008\/10\/p10008.","journal-title":"J Stat Mech Theory Exp"},{"issue":"3","key":"3966_CR33","doi-asserted-by":"publisher","first-page":"032801","DOI":"10.1103\/PhysRevE.92.032801","volume":"92","author":"VA Traag","year":"2015","unstructured":"Traag VA. Faster unfolding of communities: speeding up the Louvain algorithm. Phys Rev E. 2015;92(3):032801. https:\/\/doi.org\/10.1103\/PhysRevE.92.032801. arXiv:1503.01322D.","journal-title":"Phys Rev E"},{"issue":"2","key":"3966_CR34","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1140\/epjb\/e2010-00261-8","volume":"77","author":"TS Evans","year":"2010","unstructured":"Evans TS, Lambiotte R. Line graphs of weighted networks for overlapping communities. Eur Phys J B. 2010;77(2):265\u201372. https:\/\/doi.org\/10.1140\/epjb\/e2010-00261-8.","journal-title":"Eur Phys J B"},{"key":"3966_CR35","volume-title":"How to detect and handle outliers","author":"B Iglewicz","year":"1993","unstructured":"Iglewicz B, Hoaglin DC. How to detect and handle outliers, vol. 16. Milwaukee: ASQ Press; 1993."},{"key":"3966_CR36","doi-asserted-by":"publisher","unstructured":"Median absolute deviation, p. 348. Springer, New York (2008). https:\/\/doi.org\/10.1007\/978-0-387-32833-1_261.","DOI":"10.1007\/978-0-387-32833-1_261"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-03966-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-021-03966-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-03966-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T18:03:37Z","timestamp":1613153017000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-021-03966-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,12]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["3966"],"URL":"https:\/\/doi.org\/10.1186\/s12859-021-03966-3","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,12]]},"assertion":[{"value":"28 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"66"}}