{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:40:46Z","timestamp":1760244046243,"version":"build-2065373602"},"reference-count":6,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2008,10,9]],"date-time":"2008-10-09T00:00:00Z","timestamp":1223510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of l points in a 3D space, where l is a fixed natural number. Two structural fragments f1 and f2 are equivalent if and only if f1 = f2 x R + \u03c4 under some rotation R and translation \u03c4 . We consider the distance between two structural fragments to be the sum of the squared Euclidean distance between all corresponding points of the structural fragments. Given a set of n structural fragments, we consider the problem of finding k (or fewer) structural fragments g1, g2, ... , gk, so as to minimize the sum of the distances between each of f1, f2, ... , fn to its nearest structural fragment in g1, ... , gk. In this paper we show a polynomial-time approximation scheme (PTAS) for the problem through a simple sampling strategy.<\/jats:p>","DOI":"10.3390\/a1020043","type":"journal-article","created":{"date-parts":[[2008,10,10]],"date-time":"2008-10-10T09:51:21Z","timestamp":1223632281000},"page":"43-51","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A PTAS For The k-Consensus Structures Problem Under Squared Euclidean Distance"],"prefix":"10.3390","volume":"1","author":[{"given":"Shuai Cheng","family":"Li","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada N2L 3G1"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yen Kaow","family":"Ng","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka 819-0395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore 117543"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2008,10,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","article-title":"Data clustering: a review","volume":"31(3)","author":"Jain","year":"1999","journal-title":"ACM Computing Surveys"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1109\/TPAMI.1987.4767965","article-title":"Least-squares fitting of two 3-d point sets","volume":"9(5)","author":"Arun","year":"1987","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1109\/34.88573","article-title":"Least-squares estimation of transformation parameters between two point patterns","volume":"13(4)","author":"Umeyama","year":"1991","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ma, B., and Zhang, K.Z. (2007). Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings, Springer.","DOI":"10.1007\/978-3-540-73437-6"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6614","DOI":"10.1073\/pnas.89.14.6614","article-title":"Effects of compact volume and chain stiffness on the conformations of native proteins","volume":"89","author":"Hao","year":"1992","journal-title":"Proc. Natl. Acad. Sci."},{"key":"ref_6","first-page":"506","article-title":"A revised proof of the metric properties of optimally superimposed vector sets","volume":"58(5)","author":"Boris","year":"2002","journal-title":"Acta Crystallographica Section A"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/1\/2\/43\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:21:02Z","timestamp":1760221262000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/1\/2\/43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,9]]},"references-count":6,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2008,12]]}},"alternative-id":["a1020043"],"URL":"https:\/\/doi.org\/10.3390\/a1020043","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2008,10,9]]}}}