{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:10:01Z","timestamp":1738350601417,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705987"},{"type":"electronic","value":"9783540706007"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70600-7_37","type":"book-chapter","created":{"date-parts":[[2008,8,29]],"date-time":"2008-08-29T15:14:34Z","timestamp":1220022874000},"page":"479-488","source":"Crossref","is-referenced-by-count":1,"title":["An Algorithm for Multiple and Global Alignments"],"prefix":"10.1007","author":[{"given":"Mourad","family":"Elloumi","sequence":"first","affiliation":[]},{"given":"Ahmed","family":"Mokaddem","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","unstructured":"Sagot, M.F.: Ressemblance Lexicale et Structurale Entre Macromol\u00e9cules -Formalisation et Approches Combinatoires, Th\u00e8se de Doctorat, Universit\u00e9 de Marne-La-Vall\u00e9e, France (1996)"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S.: Transforming Men Into Mice a Computationnal Theory of Genome Rearrangements, PhD Thesis, The Pennsylvania State University (1995)","DOI":"10.1007\/BFb0015244"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming Cabbage Into Turnip (Polynomial Algorithm for Srting Signed Permutations By Reversals). In: Proc. 27th Annual ACM Symposium on the Theory of Computing, pp. 178\u2013189 (1995)","DOI":"10.1145\/225058.225112"},{"key":"37_CR4","unstructured":"Christie, D.: Genome Rearrangement Problems Ph.D Thesis, University of Glasgow (1998)"},{"issue":"22","key":"37_CR5","doi-asserted-by":"publisher","first-page":"10881","DOI":"10.1093\/nar\/16.22.10881","volume":"16","author":"F. Corpet","year":"1988","unstructured":"Corpet, F.: Multiple Sequence Alignment With Hierarchical Clustering. Nucleic Acids Research\u00a016(22), 10881\u201310890 (1988)","journal-title":"Nucleic Acids Research"},{"issue":"5","key":"37_CR6","first-page":"501","volume":"8","author":"E. Depiereux","year":"1992","unstructured":"Depiereux, E., Feytmans, E.: MATCH-BOX - A fundamentally new Algorithm for The Simultaneous Alignment of Several Protein Sequences. Comput. Appl. Biosci.\u00a08(5), 501\u2013509 (1992)","journal-title":"Comput. Appl. Biosci."},{"issue":"11","key":"37_CR7","doi-asserted-by":"publisher","first-page":"2478","DOI":"10.1093\/nar\/30.11.2478","volume":"30","author":"A.L. Delcher","year":"2002","unstructured":"Delcher, A.L., Phillippy, A., Carlton, J., Salzberg, S.L.: Fast Algorithms for Large-ScaleGenome Alignment and Comparison. Nucleic Acids Research\u00a030(11), 2478\u20132483 (2002)","journal-title":"Nucleic Acids Research"},{"key":"37_CR8","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C. Lee","year":"2002","unstructured":"Lee, C., Grasso, C., Sharlow, M.: Multiple Sequence Alignment UingPpartial Order Graphs. Bioinformatics\u00a0(18), 452\u2013464 (2002)","journal-title":"Bioinformatics"},{"issue":"66","key":"37_CR9","first-page":"1","volume":"4","author":"M. Brudno","year":"2003","unstructured":"Brudno, M., Chapman, M., G\u00f6ttgens, B., Batzoglou, S., Morgenstern, B.: Fast and Sensitive Multiple Alignment of Large Genomic Sequences. BMC Bioinformatics\u00a04(66), 1\u201311 (2003)","journal-title":"BMC Bioinformatics"},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1101\/gr.1960404","volume":"14","author":"N. Bray","year":"2004","unstructured":"Bray, N., Pachter, L.: MAVID: Constrained Ancestral Alignment of Multiple Sequences. Genome Research\u00a0(14), 693\u2013699 (2004)","journal-title":"Genome Research"},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1186\/1471-2105-6-298","volume":"6","author":"T. Lassmann","year":"2005","unstructured":"Lassmann, T., Sonnhammer, E.: Kalign: An Accurate and Fast Multiple Sequence Alignment Algorithm. BMC Bioinformatics\u00a0(6), 298 (2005)","journal-title":"BMC Bioinformatics"},{"key":"37_CR12","unstructured":"Schwartz, A., Pachter, L.: Multiple Alignment by Sequence Annealing. Bioinformatics (2006)"},{"key":"37_CR13","doi-asserted-by":"publisher","first-page":"2098","DOI":"10.1073\/pnas.93.22.12098","volume":"93","author":"B. Morgenstern","year":"1996","unstructured":"Morgenstern, B., Dress, A., Werner, T.: Multiple DNA and Protein Sequence Alignment Based on Segment-to-Segment Comparison. Proc. Natl. Acad. Sci. U.S.A.\u00a0(93), 2098\u201312103 (1996)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"issue":"3","key":"37_CR14","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1093\/bioinformatics\/14.3.290","volume":"14","author":"B. Morgenstern","year":"1998","unstructured":"Morgenstern, B., Frech, K., Dress, A., Werner, T.: DIALIGN: Finding Local Similarities by Multiple Sequence Alignment. Bioinformatics\u00a014(3), 290\u2013294 (1998)","journal-title":"Bioinformatics"},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1093\/bioinformatics\/15.3.203","volume":"15","author":"H.P. Lenhof","year":"1999","unstructured":"Lenhof, H.P., Morgenstern, B., Reinert, K.: An Exact Solution for The Segment-to-Segment Multiple Sequence Alignment Problem. Bioinformatics\u00a0(15), 203\u2013210 (1999)","journal-title":"Bioinformatics"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Schwartz, S., Kent, W.J., Smit, A., Zhang, Z.: Human-Mouse Alignments with Blastz. Genome Research, 103\u2013107 (2003)","DOI":"10.1101\/gr.809403"},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1101\/gr.926603","volume":"13","author":"M. Brudno","year":"2003","unstructured":"Brudno, M., Do, C.B., Cooper, G.M., Kim, M.F., Davydov, E., Green, E.D., Sidow, A., Batzoglou, S.: LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA. Genome Research\u00a0(13), 721\u2013731 (2003)","journal-title":"Genome Research"},{"issue":"1","key":"37_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1093\/nar\/gkh169","volume":"32","author":"M.C. Frith","year":"2004","unstructured":"Frith, M.C., Hansen, U., Spouge, J.L.: Finding Functional Sequence Elements by Multiple Local Alignments. Nucleic Acids Research\u00a032(1), 189\u2013200 (2004)","journal-title":"Nucleic Acids Research"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Morgenstern, B.: DIALIGN: Multiple DNA and Protein Sequence Alignment at BiBiServ. Nucleic Acids Research\u00a032(Web Server Issue) (2004)","DOI":"10.1093\/nar\/gkh373"},{"key":"37_CR20","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1101\/gr.3007205","volume":"15","author":"I. Ovcharenko","year":"2005","unstructured":"Ovcharenko, I., Loots, G.G., Giardine, B.M., Hou, M., Ma, J., Hardison, R.C., Stubbs, L., Millers, W.: Mulan: Multiple-Sequence Local Alignment and Visualization for Studying Function and Evolution. Genome Research\u00a0(15), 184\u2013194 (2005)","journal-title":"Genome Research"},{"key":"37_CR21","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A General Method Applicable to the Search for Similarities in The Amino-Acid Sequence of two Proteins. Journal of Molecular Biolog\u00a0(48), 443\u2013453 (1970)","journal-title":"Journal of Molecular Biolog"},{"issue":"6","key":"37_CR22","doi-asserted-by":"crossref","first-page":"1381","DOI":"10.1287\/opre.32.6.1381","volume":"32","author":"T.H. Byers","year":"1984","unstructured":"Byers, T.H., Waterman, M.S.: Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming. Operations Research\u00a032(6), 1381\u20131384 (1984) Operations Research Society of America (Eds.)","journal-title":"Operations Research"},{"key":"37_CR23","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0025-5564(85)90096-3","volume":"77","author":"M.S. Waterman","year":"1985","unstructured":"Waterman, M.S., Byers, T.H.: A Dynamic Programming Algorithm to Find All Solutions in a Neighborhood of The Optimum. Mathematical Biosciences\u00a0(77), 179\u2013188 (1985)","journal-title":"Mathematical Biosciences"},{"key":"37_CR24","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/0022-2836(91)80062-Y","volume":"221","author":"M. Zuker","year":"1991","unstructured":"Zuker, M.: Suboptimal Sequence Alignment in Molecular biology: 1nalysis with Errors. J. Mol. Biol.\u00a0221, 403\u2013420 (1991)","journal-title":"J. Mol. Biol."},{"key":"37_CR25","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1089\/cmb.1994.1.349","volume":"4","author":"D. Naor","year":"1994","unstructured":"Naor, D., Brutlag, D.L.: On Near-Optimal Alignments of Biological Sequences. J. Comp. Biol.\u00a0(4), 349\u2013366 (1994)","journal-title":"J. Comp. Biol."},{"issue":"22","key":"37_CR26","doi-asserted-by":"publisher","first-page":"4633","DOI":"10.1093\/nar\/29.22.4633","volume":"29","author":"S. Kurtz","year":"2001","unstructured":"Kurtz, S., Ohlebusch, E., Schleiermacher, C., Stoye, J.: Reputer: The Manifold Applications of Repeat Analysis. Nucleic Acids Research\u00a029(22), 4633\u20134642 (2001)","journal-title":"Nucleic Acids Research"},{"key":"37_CR27","unstructured":"No\u00e9, L.: Recherche de Similarit\u00e9s dans Les S\u00e9quences d\u2019ADN: Mod\u00e8les et Algorithmes pour la Conception de Graines Efficaces, Th\u00e9se de Doctorat, Universit\u00e9 Henri Poincar\u00e9 (2005)"},{"issue":"1","key":"37_CR28","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1093\/bioinformatics\/bti772","volume":"22","author":"W. Huang","year":"2006","unstructured":"Huang, W., Umbach, D.M., Leping, L.: Accurate Anchoring Alignment of Divergent Sequences. Bioinformatics,\u00a022(1), 29\u201334 (2006)","journal-title":"Bioinformatics,"},{"key":"37_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, X., Kahveci, T.: A New Approach for Alignment of Multiple Proteins. In: Pacific Symposium on Biocomputing, vol.\u00a011, pp. 339\u2013350 (2006)","DOI":"10.1142\/9789812701626_0031"},{"issue":"5","key":"37_CR30","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"R.C. Edgar","year":"2004","unstructured":"Edgar, R.C.: MUSCLE: Multiple Sequence Alignment with High Accuracy and High throughput. Nucleic Acids Research\u00a032(5), 1792\u20131797 (2004)","journal-title":"Nucleic Acids Research"},{"issue":"1","key":"37_CR31","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1093\/nar\/gni171","volume":"33","author":"Y. Liang Ye","year":"2005","unstructured":"Liang Ye, Y., Huang, X.: MAP2: Multiple Alignments of Syntenic Genomic sequences. Nucleic Acids Research\u00a033(1), 162\u2013170 (2005)","journal-title":"Nucleic Acids Research"},{"issue":"8","key":"37_CR32","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Cybernetics and Control Theory\u00a010(8), 707\u2013710 (1966)","journal-title":"Cybernetics and Control Theory"},{"key":"37_CR33","first-page":"60","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms, pp. 60\u201365. Addison-Wesley Publishing Company, Reading (1974)"},{"key":"37_CR34","doi-asserted-by":"crossref","unstructured":"Karp, R., Miller, R.E., Rosenberg, A.L.: Rapid Identification of Repeated Patterns in Strings, Trees and Arrays. In: 4th symposium of theory of Computing, pp. 125\u2013136 (1972)","DOI":"10.1145\/800152.804905"},{"key":"37_CR35","unstructured":"RNA Families Database of Alignments and CMs http:\/\/www.sanger.ac.uk\/Software\/Rfam"},{"key":"37_CR36","unstructured":"Protein Families Database, http:\/\/www.sanger.ac.uk\/Software\/Pfam"},{"key":"37_CR37","unstructured":"National Center for Biotechnology Information, http:\/\/www.ncbi.nlm.nih.gov"},{"issue":"3","key":"37_CR38","first-page":"345","volume":"5","author":"M.O. Dayhoff","year":"1979","unstructured":"Dayhoff, M.O., Schwartz, R.M., Orcutt, B.C.: A Model for Evolutionary Change. Atlas of Protein Sequence and Structure\u00a05(3), 345\u2013352 (1979)","journal-title":"Atlas of Protein Sequence and Structure"},{"key":"37_CR39","doi-asserted-by":"publisher","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","volume":"89","author":"S. Henikoff","year":"1992","unstructured":"Henikoff, S., Henikoff, J.G.: Amino Acid Substitution Matrices From Protein Blocks. Proc. Natl. Acad. Sci. U.S.A.\u00a089, 10915\u201310919 (1992)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."}],"container-title":["Communications in Computer and Information Science","Bioinformatics Research and Development"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70600-7_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:48:36Z","timestamp":1738349316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70600-7_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705987","9783540706007"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70600-7_37","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[]}}