{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T15:35:42Z","timestamp":1742398542306},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T00:00:00Z","timestamp":1175731200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T00:00:00Z","timestamp":1175731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cluster Comput"],"published-print":{"date-parts":[[2007,6]]},"DOI":"10.1007\/s10586-007-0020-0","type":"journal-article","created":{"date-parts":[[2007,4,4]],"date-time":"2007-04-04T19:09:35Z","timestamp":1175713775000},"page":"187-202","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["An exact parallel algorithm to compare very long biological sequences in clusters of workstations"],"prefix":"10.1007","volume":"10","author":[{"given":"Azzedine","family":"Boukerche","sequence":"first","affiliation":[]},{"given":"Alba Cristina Magalhaes Alves","family":"de Melo","sequence":"additional","affiliation":[]},{"given":"Edans Flavius de Oliveira","family":"Sandes","sequence":"additional","affiliation":[]},{"given":"Mauricio","family":"Ayala-Rincon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,4,5]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"214","author":"S.F. Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Molec. Biol. 214, 403\u2013410 (1990)","journal-title":"J. Molec. Biol."},{"key":"20_CR2","volume-title":"Proc. of the IEEE\/ACM Int. Symp. on Cluster Computing and the Grid","author":"R.B. Batista","year":"2004","unstructured":"Batista, R.B., Silva, D.N., Melo, A.C.M.A., Weigang, L.: Using a dsm application to locally align dna sequences. In: Proc. of the IEEE\/ACM Int. Symp. on Cluster Computing and the Grid. IEEE Computer Society, Los Alamitos (2004)"},{"key":"20_CR3","first-page":"149","volume-title":"Parallel Computing for Bioinformatics and Computational Biology","author":"A. Boukerche","year":"2006","unstructured":"Boukerche, A., Melo, A.C.M.A.: Computational Molecular Biology. In: Zomaya, A.Y. (ed.) Parallel Computing for Bioinformatics and Computational Biology, pp.\u00a0149\u2013165. Wiley Interscience, Hoboken (2006)"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/11427186_40","volume-title":"4th Int. Workshop on Experimental and Efficient Algorithms","author":"A. Boukerche","year":"2005","unstructured":"Boukerche, A., Melo, A.C.M.A., Ayala-Rincon, M., Santana, T.M.: Parallel smith-waterman algorithm for local dna comparison in a cluster of workstations. In: 4th Int. Workshop on Experimental and Efficient Algorithms. Lecture Notes in Computer Science, vol.\u00a03530, pp.\u00a0464\u2013475. Springer, Heidelberg (2005)"},{"key":"20_CR5","volume-title":"Proc. of the Int. Parallel and Distributed Processing Symposium (IPDPS2004)","author":"A. Boukerche","year":"2004","unstructured":"Boukerche, A., Melo, A.C.M.A., Walter, M.E.M.T., Melo, R.C.F., Santana, M.N.P., Batista, R.B.: Performance evaluation of a local dna sequence alignment algorithm on a cluster of workstations. In: Proc. of the Int. Parallel and Distributed Processing Symposium (IPDPS2004). IEEE Society, Los Alamitos (2004)"},{"key":"20_CR6","unstructured":"Chang, W.I., Lawler, E.W.: Approximate string matching in sublinear expected time. In: IEEE Thirty-first Annual Symposium on Foundations of Computer Science, 1990, pp.\u00a0116\u2013124"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Chen, C., Schmidt, B.: Computing large-scale alignments on a multi-cluster. In: IEEE International Conference on Cluster Computing, 2003","DOI":"10.1109\/CLUSTR.2003.1253297"},{"issue":"1","key":"20_CR8","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1093\/nar\/12.1Part1.175","volume":"12","author":"J. Fickett","year":"1984","unstructured":"Fickett, J.: Fast optimal alignments. Nucleic Acids Res. 12(1), 175\u2013179 (1984)","journal-title":"Nucleic Acids Res."},{"key":"20_CR9","unstructured":"Galper, A.R., Brutlag, D.R.: Parallel similarity search and alignment with the dynamic programming method. Technical Report KSL 90-74, Stanford University, 1990, pp.\u00a01\u201314"},{"key":"20_CR10","doi-asserted-by":"crossref","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. Press Syndicate of the University of Cambridge, New York (1997)"},{"issue":"6","key":"20_CR11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341\u2013343 (1975)","journal-title":"Commun. ACM"},{"key":"20_CR12","first-page":"463","volume-title":"High Performance Computing and Networking (HPCN)","author":"S. Hu","year":"1999","unstructured":"Hu, S., Shi, W., Tang, Z.: Jiajia: An svm system based on a new cache coherence protocol. In: High Performance Computing and Networking (HPCN), pp.\u00a0463\u2013472. Springer, Heidelberg (1999)"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0196-8858(91)90017-D","volume":"12","author":"X. Huang","year":"1991","unstructured":"Huang, X., Miller, W.: A time efficient, linear-space local similarity algorithm. Adv. Appl. Math. 12, 337\u2013357 (1991)","journal-title":"Adv. Appl. Math."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Landau, G., Viskin, U.: Introducing efficient parallelism into approximate string matching and new serial algorithm. In: 18th ACM STOC, 1986, pp.\u00a0220\u2013230","DOI":"10.1145\/12130.12152"},{"key":"20_CR15","unstructured":"Martins, W.S., Cuvillo, J.B.D., Useche, F.J., Theobald, K.B., Gao, G.R.: A multithread parallel implementation of a dynamic programming algorithm for sequence comparison. In: Brazilian Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2001, pp.\u00a01\u20138"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/978-3-540-45209-6_74","volume-title":"Euro-Par 2003: Parallel Processing","author":"R. Melo","year":"2003","unstructured":"Melo, R., Walter, M.E.T., Melo, A.C.M.A., Batista, R.B.: Comparing two long dna sequences using a dsm system. In: Euro-Par 2003: Parallel Processing. Lecture Notes in Computer Science, vol.\u00a02790, pp.\u00a0517\u2013524. Springer, Heidelberg (2003)"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E.W. Myers","year":"1986","unstructured":"Myers, E.W.: An o(nd) difference algorithm and its variations. Algorithmica 1, 251\u2013266 (1986)","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"key":"20_CR19","unstructured":"NCBI: Ncbi homepage. Website, http:\/\/www.ncbi.nlm.nih.gov\/, Nov.\u00a02004"},{"key":"20_CR20","unstructured":"NCBI: Submit to genbank. Website, http:\/\/www.ncbi.nlm.nih.gov\/Genbank\/index.html, Nov.\u00a02004"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S. Needleman","year":"1970","unstructured":"Needleman, S., Wunsch, C.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48, 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"W.R. Pearson","year":"1988","unstructured":"Pearson, W.R., Lipman, D.J.: Improved tools for biological sequence analysis. Proc. Natl. Acad. Sci. USA 85, 2444\u20132448 (1988)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"20_CR23","volume-title":"Search of Clusters\u2014The Coming Battle for Lowly Parallel Computing","author":"G. Pfister","year":"1995","unstructured":"Pfister, G.: In: Search of Clusters\u2014The Coming Battle for Lowly Parallel Computing. Prentice-Hall, Upper Saddle River (1995)"},{"issue":"12","key":"20_CR24","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1109\/TPDS.2004.86","volume":"15","author":"S. Rajko","year":"2004","unstructured":"Rajko, S., Aluru, S.: Space and time optimal parallel sequence alignments. IEEE Trans. Parallel Distributed Syst. 15(12), 1070\u20131081 (2004)","journal-title":"IEEE Trans. Parallel Distributed Syst."},{"key":"20_CR25","volume-title":"Introduction to Computational Molecular Biology","author":"J.C. Setubal","year":"1997","unstructured":"Setubal J.C., Meidanis J.: Introduction to Computational Molecular Biology. Brooks\/Cole, Boston (1997)"},{"key":"20_CR26","unstructured":"Shao, G.: Adaptive scheduling of master\/worker applications on distributed computational resources. PhD thesis, University of California at San Diego (2001)"},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. Smith","year":"1981","unstructured":"Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"20_CR28","unstructured":"Tang, P., Yew, P.C.: Processor self-scheduling for multiple nested parallel loops. In: Int. Conf. on Parallel Processing (ICPP), 1986, pp.\u00a0528\u2013535"},{"issue":"1","key":"20_CR29","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E. Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Algorithms for approximate string matching. Inf. Control 64(1), 100\u2013118 (1985)","journal-title":"Inf. Control"},{"key":"20_CR30","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1109\/ICAPP.2002.1173568","volume-title":"Fifth Int. Conf. on Algorithm and Architectures for Parallel Processing (ICA3PP02)","author":"F. Zhang","year":"2002","unstructured":"Zhang, F., Qiao, X., Liu, Z.: A parallel smith waterman algorithm based on divide and conquer. In: Fifth Int. Conf. on Algorithm and Architectures for Parallel Processing (ICA3PP02), pp.\u00a0162\u2013169. IEEE Society, Los Alamitos (2002)"}],"container-title":["Cluster Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-007-0020-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10586-007-0020-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-007-0020-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-007-0020-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T05:43:48Z","timestamp":1652852628000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10586-007-0020-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,5]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["20"],"URL":"https:\/\/doi.org\/10.1007\/s10586-007-0020-0","relation":{},"ISSN":["1386-7857","1573-7543"],"issn-type":[{"value":"1386-7857","type":"print"},{"value":"1573-7543","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,4,5]]},"assertion":[{"value":"5 April 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}