{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T11:54:32Z","timestamp":1720698872519},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Given a set <jats:italic>S<\/jats:italic> of <jats:italic>n<\/jats:italic> locally aligned sequences, it is a needed prerequisite to partition it into groups of very similar sequences to facilitate subsequent computations, such as the generation of a phylogenetic tree. This article introduces a new method of clustering which partitions <jats:italic>S<\/jats:italic> into subsets such that the overlap of each pair of sequences within a subset is at least a given percentage <jats:italic>c<\/jats:italic> of the lengths of the two sequences. We show that this problem can be reduced to finding all maximal cliques in a special kind of max-tolerance graph which we call a <jats:italic>c-max-tolerance<\/jats:italic> graph. Previously we have shown that finding all maximal cliques in general max-tolerance graphs can be done efficiently in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup> + <jats:italic>out<\/jats:italic>). Here, using a new kind of sweep-line algorithm, we show that the restriction to <jats:italic>c<\/jats:italic>-max-tolerance graphs yields a better runtime of <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup> log <jats:italic>n<\/jats:italic> + <jats:italic>out<\/jats:italic>). Furthermore, we present another algorithm which is much easier to implement, and though theoretically slower than the first one, is still running in polynomial time. We then experimentally analyze the number and structure of all maximal cliques in a <jats:italic>c<\/jats:italic>-max-tolerance graph, depending on the chosen <jats:italic>c<\/jats:italic>-value. We apply our simple algorithm to artificial and biological data and we show that this implementation is much faster than the well-known application Cliquer. By introducing a new heuristic that uses the set of all maximal cliques to partition <jats:italic>S<\/jats:italic>, we finally show that the computed partition gives a reasonable clustering for biological data sets.<\/jats:p>","DOI":"10.1186\/1748-7188-1-9","type":"journal-article","created":{"date-parts":[[2006,5,31]],"date-time":"2006-05-31T22:02:07Z","timestamp":1149112927000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences"],"prefix":"10.1186","volume":"1","author":[{"given":"Katharina A","family":"Lehmann","sequence":"first","affiliation":[]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Stephan","family":"Steigele","sequence":"additional","affiliation":[]},{"given":"Kay","family":"Nieselt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,31]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S Altschul","year":"1990","unstructured":"Altschul S, Gish W, Miller W, Myers E, Lipman D: Basic Local Alignment Search Tool. J Mol Biol. 1990, 215: 403-410. 10.1006\/jmbi.1990.9999","journal-title":"J Mol Biol"},{"key":"9_CR2","unstructured":"NCBI-Blast.  http:\/\/www.ncbi.nlm.nih.gov\/BLAST\/"},{"key":"9_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511542985","volume-title":"Tolerance Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC, Trenk AN: Tolerance Graphs. 2004, Cambridge University Press"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S Benzer","year":"1959","unstructured":"Benzer S: On the Topology of the Genetic Fine Structure. PNAS. 1959, 45: 1607-1620. 10.1073\/pnas.45.11.1607","journal-title":"PNAS"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson D, Gross O: Incidence matrices and interval graphs. Pacific J Math. 1965, 15: 835-855.","journal-title":"Pacific J Math"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K Booth","year":"1976","unstructured":"Booth K, Lueker G: Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms. J Comput Sys Sci. 1976, 13: 335-379.","journal-title":"J Comput Sys Sci"},{"key":"9_CR7","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS: Computers and Intractability. 1979, WH Freeman and Company"},{"key":"9_CR8","volume-title":"Tech. Rep. Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland","author":"S Niskanen","year":"2003","unstructured":"Niskanen S, \u00d6sterg\u00e5rd PR: Cliquer User's Guide, Version 1.0. Tech. Rep. Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland. 2003"},{"key":"9_CR9","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '06)","author":"M Kaufmann","year":"2006","unstructured":"Kaufmann M, Kratochv\u00edl J, Lehmann KA, Subramanian AR: Max-Tolerance Graphs as Intersection Graphs: Cliques, Cycles, and Recognition. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '06). 2006"},{"key":"9_CR10","volume-title":"Algorithm Design","author":"J Kleinberg","year":"2006","unstructured":"Kleinberg J, Tardos \u00c9: Algorithm Design. 2006, Addison-Wesley"},{"issue":"Database Issue","key":"9_CR11","doi-asserted-by":"publisher","first-page":"D154","DOI":"10.1093\/nar\/gki070","volume":"33","author":"A Bairoch","year":"2005","unstructured":"Bairoch A, Apweiler R, Wu C, Barker W, Boeckmann B, Ferro S, Gasteiger E, Huang H, Lopez R, Magrane M, Martin M, Natale D, O'donovan C, Redaschi N, Yeh L: The Universal Protein Resource (UniProt). Nucleic Acids Research. 2005, 33 (Database Issue): D154-D159. 10.1093\/nar\/gki070","journal-title":"Nucleic Acids Research"},{"key":"9_CR12","volume-title":"Computational Geometry","author":"M de Berg","year":"1991","unstructured":"de Berg M, van Kreveld M, Overmars M, Schwarzkopf O: Computational Geometry. 1991, Springer Verlag, Heidelberg"},{"key":"9_CR13","first-page":"715","volume-title":"Mol Genet Genomics","author":"J Srinivasan","year":"2003","unstructured":"Srinivasan J, Sinz W, Jesse T, Wiggers-Perebolte L, Jansen K, Buntjer J, van der Meulen M, Sommer R: An integrated physical and genetic map of the nematode Pristionchus paciflcus. Mol Genet Genomics. 2003, 715-22. 10.1007\/s00438-003-0881-8"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-1-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T22:45:07Z","timestamp":1630449907000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-1-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,31]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["9"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-1-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5,31]]},"assertion":[{"value":"17 February 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2006","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2006","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}