{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:29Z","timestamp":1750307189705,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007458","name":"Qatar Foundation","doi-asserted-by":"publisher","award":["FA9550-09-1-0223"],"award-info":[{"award-number":["FA9550-09-1-0223"]}],"id":[{"id":"10.13039\/100007458","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0915436, CNS-0913875"],"award-info":[{"award-number":["CNS-0915436, CNS-0913875"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            This article presents a new algorithm for finding oligonucleotide signatures that are specific and sensitive for organisms or groups of organisms in large-scale sequence datasets. We assume that the organisms have been organized in a hierarchy, for example, a phylogenetic tree. The resulting signatures, binding sites for primers and probes, match the maximum possible number of organisms in the target group while having at most\n            <jats:italic>k<\/jats:italic>\n            matches outside of the target group.\n          <\/jats:p>\n          <jats:p>The key step in the algorithm is the use of the lowest common ancestor (LCA) to search the organism hierarchy; this allows the combinatorial problem in almost linear time (empirically observed) to be solved. The presented algorithm improves performance by several orders of magnitude in terms of both memory consumption and runtime when compared to the best-known previous algorithms while giving identical, exact solutions.<\/jats:p>\n          <jats:p>This article gives a formal description of the algorithm, discusses details of our concrete, publicly available implementation, and presents the results from our performance evaluation.<\/jats:p>","DOI":"10.1145\/2133803.2212315","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T12:50:57Z","timestamp":1350391857000},"source":"Crossref","is-referenced-by-count":0,"title":["Efficient relaxed search in hierarchically clustered sequence datasets"],"prefix":"10.1145","volume":"17","author":[{"given":"Kai C.","family":"Bader","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Germany"}]},{"given":"Mikhail J.","family":"Atallah","sequence":"additional","affiliation":[{"name":"Purdue University, IN"}]},{"given":"Christian","family":"Grothoff","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2012,7,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrmicro1888"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1128\/mr.59.1.143-169.1995","article-title":"Phylogenetic identification and in situ detection of individual microbial cells without cultivation","volume":"59","author":"Amann R. I.","year":"1995","journal-title":"Microbiol Rev."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Bader K. C. Eissler T. Evans N. GauthierDickey C. Grothoff C. Grothoff K. Keene J. Meier H. Ritzdorf C. and \n      \n      \n      Rutherford M. J\n      \n  \n  . \n  2010\n  . Distributed stream processing with DUP. In Network and Parallel Computing Lecture Notes in Computer Science vol. \n  6289 Springer Berlin 232--246.   Bader K. C. Eissler T. Evans N. GauthierDickey C. Grothoff C. Grothoff K. Keene J. Meier H. Ritzdorf C. and Rutherford M. J. 2010. Distributed stream processing with DUP. In Network and Parallel Computing Lecture Notes in Computer Science vol. 6289 Springer Berlin 232--246.","DOI":"10.1007\/978-3-642-15672-4_21"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btr161"},{"volume":"226","volume-title":"Methods in Molecular Biology Series","author":"Bartlett J. M. S.","key":"e_1_2_1_6_1"},{"volume-title":"LATIN 2000: Theoretical Informatics","author":"Bender M.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti673"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkn879"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1128\/AEM.03006-05"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-11"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkp073"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btr483"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btm114"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2164-11-434"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Fischer J.\n     and \n      \n      \n      Heun V\n      \n  \n  . \n  2007\n  . A new succinct representation of rmq-information and improvements in the enhanced suffix array. In Combinatorics Algorithms Probabilistic and Experimental Methodologies B. Chen M. Paterson and G. Zhang Eds. Lecture Notes in Computer Science vol. \n  4614 Springer Berlin 459--470.   Fischer J. and Heun V. 2007. A new succinct representation of rmq-information and improvements in the enhanced suffix array. In Combinatorics Algorithms Probabilistic and Experimental Methodologies B. Chen M. Paterson and G. Zhang Eds. Lecture Notes in Computer Science vol. 4614 Springer Berlin 459--470.","DOI":"10.1007\/978-3-540-74450-4_41"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2004-5-2-r12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-11-132"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Loy A. Maixner F. Wagner M. and Horn M. 2007. probeBase--an online resource for rRNA-targeted oligonucleotide probes: new features 2007. Nucleic Acids Res. 35 (Database issue) D800--804.  Loy A. Maixner F. Wagner M. and Horn M. 2007. probeBase--an online resource for rRNA-targeted oligonucleotide probes: new features 2007. Nucleic Acids Res. 35 (Database issue) D800--804.","DOI":"10.1093\/nar\/gkl856"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh293"},{"key":"e_1_2_1_23_1","unstructured":"Olsen G. 1990. The \u201cNewick's 8:45\u201d tree format. http:\/\/evolution.genetics.washington.edu\/phylip\/newick_doc.html.  Olsen G. 1990. The \u201cNewick's 8:45\u201d tree format. http:\/\/evolution.genetics.washington.edu\/phylip\/newick_doc.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04031-3_23"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkp286"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0030098"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0009490"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkm864"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkr732"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1128\/aem.54.5.1079-1084.1988","article-title":"Use of phylogenetically based hybridization probes for studies of ruminal microbial ecology","volume":"54","author":"Stahl D. A.","year":"1988","journal-title":"Appl. Environ. Microbiol."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl446"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2212315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2212315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:05:52Z","timestamp":1750241152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2212315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":31,"alternative-id":["10.1145\/2133803.2212315"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2212315","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}