{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:50Z","timestamp":1759638530893},"reference-count":21,"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":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>The discovery of surprisingly frequent patterns is of paramount interest in bioinformatics and computational biology. Among the patterns considered, those consisting of pairs of solid words that co-occur within a prescribed maximum distance -or<jats:italic>gapped factors<\/jats:italic>- emerge in a variety of contexts of DNA and protein sequence analysis. A few algorithms and tools have been developed in connection with specific formulations of the problem, however, none can handle comprehensively each of the multiple ways in which the distance between the two terms in a pair may be defined.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>This paper presents efficient algorithms and tools for the extraction of all pairs of words up to an arbitrarily large length that co-occur surprisingly often in close proximity within a sequence. Whereas the number of such pairs in a sequence of<jats:italic>n<\/jats:italic>characters can be \u0398(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>), it is shown that an exhaustive discovery process can be carried out in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) or<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>), depending on the way distance is measured. This is made possible by a prudent combination of properties of pattern maximality and monotonicity of scores, which lead to reduce the number of word pairs to be weighed explicitly, while still producing also the scores attained by any of the pairs not explicitly considered. We applied our approach to the discovery of spaced dyads in DNA sequences.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>Experiments on biological datasets prove that the method is effective and much faster than exhaustive enumeration of candidate patterns. Software is available freely by academic users via the web interface at<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/bcb.dei.unipd.it:8080\/dyweb\" ext-link-type=\"uri\">http:\/\/bcb.dei.unipd.it:8080\/dyweb<\/jats:ext-link>.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1748-7188-6-5","type":"journal-article","created":{"date-parts":[[2011,3,23]],"date-time":"2011-03-23T19:17:28Z","timestamp":1300907848000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient algorithms for the discovery of gapped factors"],"prefix":"10.1186","volume":"6","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cinzia","family":"Pizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Esko","family":"Ukkonen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,3,23]]},"reference":[{"issue":"3-4","key":"118_CR1","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1089\/10665270360688020","volume":"10","author":"A Apostolico","year":"2003","unstructured":"Apostolico A, Bock ME, Lonardi S: Monotony of surprise and large-scale quest for unusual words. Journal of Computational Biology. 2003, 10 (3-4): 238-311. 10.1089\/10665270360688020","journal-title":"Journal of Computational Biology"},{"issue":"6-7","key":"118_CR2","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/j.dam.2005.09.017","volume":"155","author":"A Apostolico","year":"2007","unstructured":"Apostolico A, Pizzi C: Motif discovery by monotone scores. Discrete Applied Mathematics, special issue Computational Molecular Biology Series. 2007, 155 (6-7): 695-706.","journal-title":"Discrete Applied Mathematics, special issue Computational Molecular Biology Series"},{"key":"118_CR3","first-page":"270","volume-title":"Proceedings of the Seventh International Conference on Discovery Science: 2-5 Oct 2004; Padova, Italy","author":"A Apostolico","year":"2004","unstructured":"Apostolico A, Pizzi C, Satta G: Optimal discovery of subword associations in strings (extended abstract). Proceedings of the Seventh International Conference on Discovery Science: 2-5 Oct 2004; Padova, Italy. Edited by: Suzuki. 2004, 270-277. Arikawa, Springer, LNAI 3245,"},{"key":"118_CR4","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1142\/S0129054108005541","volume":"19","author":"P Peterlongo","year":"2008","unstructured":"Peterlongo P, Allali J, Sagot MF: Indexing gapped factors using a tree. International Journal on Fundation of Computer Science. 2008, 19: 71-87. 10.1142\/S0129054108005541","journal-title":"International Journal on Fundation of Computer Science"},{"key":"118_CR5","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00453-007-9141-3","volume":"55","author":"CS Iliopoulos","year":"2007","unstructured":"Iliopoulos CS, Rahman MS: Indexing factors with gaps. Algorithmica. 2007, 55: 60-70. 10.1007\/s00453-007-9141-3","journal-title":"Algorithmica"},{"key":"118_CR6","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1145\/332306.332553","volume-title":"Proceedings of the Fourth Annual International Conference on Computational Molecular Biology: 8-11 April 2000; Tokyo","author":"L Marsan","year":"2000","unstructured":"Marsan L, Sagot MF: Extracting Structured Motifs Using a Suffix Tree - Algorithms and Application to Promoter Consensus Identification. Proceedings of the Fourth Annual International Conference on Computational Molecular Biology: 8-11 April 2000; Tokyo. Edited by: Shamir, Miyano, Istrail, Pevzner, Waterman. 2000, 210-219. ACM Press,"},{"key":"118_CR7","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1093\/bioinformatics\/18.suppl_1.S354","volume":"18","author":"E Eskin","year":"2002","unstructured":"Eskin E, Pevzner P: Finding composite regulatory patterns in DNA Sequences. Bioinformatics. 2002, 18: 354-363.","journal-title":"Bioinformatics"},{"key":"118_CR8","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-540-30213-1_37","volume-title":"Proceedings of the 11th Conference on String Processing and Information Retrieval: 5-8 Oct 2004; Padova, Italy","author":"A Carvalho","year":"2004","unstructured":"Carvalho A, Freitas A, Oliveira A, Sagot M: Efficient extraction of structured motifs using box-links. Proceedings of the 11th Conference on String Processing and Information Retrieval: 5-8 Oct 2004; Padova, Italy. Edited by: Apostolico, Melucci. 2004, 267-268. Springer LNCS 3246,"},{"key":"118_CR9","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/11682462_69","volume-title":"Proceedings of the LATIN 2006 - Theoretical Informatics, 7th Latin American Symposium: 20-24 March 2006; Valdivia, Chile","author":"N Pisanti","year":"2006","unstructured":"Pisanti N, Carvahlo A, Marsan L, Sagot MF: RISOTTO: Fast extraction of motifs with mismatches. Proceedings of the LATIN 2006 - Theoretical Informatics, 7th Latin American Symposium: 20-24 March 2006; Valdivia, Chile. Edited by: Correa, Hevia, Kiwi. 2006, 757-768. Springer LNCS 3887,"},{"issue":"8","key":"118_CR10","doi-asserted-by":"publisher","first-page":"1808","DOI":"10.1093\/nar\/28.8.1808","volume":"28","author":"J van Helden","year":"2000","unstructured":"van Helden J, Rios A, Collado-Vides J: Discovery regulatory elements in non-coding sequences by analysis of spaced dyads. Nucleic Acid Research. 2000, 28 (8): 1808-1818. 10.1093\/nar\/28.8.1808","journal-title":"Nucleic Acid Research"},{"key":"118_CR11","first-page":"49","volume":"28","author":"H Arimura","year":"2000","unstructured":"Arimura H, Arikawa S: Efficient discovery of optimal word-association patterns in large text databases. New Generation Computing. 2000, 28: 49-60.","journal-title":"New Generation Computing"},{"key":"118_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/191839.191863","volume-title":"Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data: 24-27 May 1994; Minneapolis, USA","author":"JL Wang","year":"1994","unstructured":"Wang JL, Chirn GW, Marr T, Shapiro B, Shasha D, Zhang K: Combinatorial pattern discovery for scientific data: some preliminary results. Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data: 24-27 May 1994; Minneapolis, USA. Edited by: Snodgrass, Winslett. 1994, 115-125. full_text. ACM press,"},{"key":"118_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume-title":"Proceedings of the 14th IEEE Annual Symposium on Switching and Automata Theory: 15-17 Oct 1973; Iowa, USA","author":"P Weiner","year":"1973","unstructured":"Weiner P: Linear pattern matching algorithms. Proceedings of the 14th IEEE Annual Symposium on Switching and Automata Theory: 15-17 Oct 1973; Iowa, USA. 1973, 1-11. IEEE Computer Society,"},{"issue":"2","key":"118_CR14","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E McCreight","year":"1976","unstructured":"McCreight E: A space-economical suffix tree construction algorithm. Journal of the ACM. 1976, 23 (2): 262-272. 10.1145\/321941.321946","journal-title":"Journal of the ACM"},{"issue":"3","key":"118_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen E: On-line construction of suffix trees. Algorithmica. 1995, 14 (3): 249-269. 10.1007\/BF01206331","journal-title":"Algorithmica"},{"key":"118_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words, Volume F12 of NATO ASI Series","author":"A Apostolico","year":"1985","unstructured":"Apostolico A: The myriad virtues of subword trees. Combinatorial Algorithms on Words, Volume F12 of NATO ASI Series. Edited by: Apostolico, Galil. 1985, 85-96. New York: Springer-Verlag,"},{"key":"118_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. 1997, Cam-bridge: Cambridge University Press,"},{"issue":"2","key":"118_CR18","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.jda.2007.02.003","volume":"7","author":"A Apostolico","year":"2009","unstructured":"Apostolico A, Satta G: Discovering subword associations in strings in time linear in the output size. Journal of Discrete Algorithms. 2009, 7 (2): 227-238. 10.1016\/j.jda.2007.02.003","journal-title":"Journal of Discrete Algorithms"},{"key":"118_CR19","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B Schieber","year":"1988","unstructured":"Schieber B, Vishkin U: On finding lowest common ancestors: simplifications and parallelizations. SIAM Journal on Computing. 1988, 17: 1253-1262. 10.1137\/0217079","journal-title":"SIAM Journal on Computing"},{"key":"118_CR20","first-page":"32","volume-title":"Proceedings of the Seventh International Conference on Discovery Science: 2-5 Oct 2004; Padova, Italy","author":"S Inenaga","year":"2004","unstructured":"Inenaga S, Bannai H, Hyyr\u00f6 H, Shinohara A, Takeda M, Nakai K, Miyano S: Finding optimal pairs of cooperative and competing Patterns with bounded distance. Proceedings of the Seventh International Conference on Discovery Science: 2-5 Oct 2004; Padova, Italy. Edited by: Suzuki, Arikawa. 2004, 32-46. Springer, LNAI 3245,"},{"key":"118_CR21","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1038\/nbt1053","volume":"23","author":"M Tompa","year":"2005","unstructured":"Tompa M, Li N, Bailey T, Church G, De Moor B, Es-kin E, Favorov A, Frith M, Fu Y, Kent W, Makeev V, AA M, Noble W, Pavesi G, Pesole G, R\u00e9gnier M, Simonis N, Sinha S, Thijs G, van Helden J, Vandenbogaert M, Weng Z, Workman C, Ye C, Zhu Z: Assessing computational tools for the discovery of transcription factor binding sites. Nature Biotechnology. 2005, 23: 137-144. 10.1038\/nbt1053","journal-title":"Nature Biotechnology"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-6-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T21:51:19Z","timestamp":1686001879000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-6-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,23]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["118"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-6-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,23]]},"assertion":[{"value":"2 March 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"5"}}