{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T00:25:40Z","timestamp":1704846340659},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,11,23]],"date-time":"2010-11-23T00:00:00Z","timestamp":1290470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2010,11,23]],"date-time":"2010-11-23T00:00:00Z","timestamp":1290470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>In this paper, we introduce a progressive corner cutting method called Reticular Alignment for multiple sequence alignment. Unlike previous corner-cutting methods, our approach does not define a compact part of the dynamic programming table. Instead, it defines a set of optimal and suboptimal alignments at each step during the progressive alignment. The set of alignments are represented with a network to store them and use them during the progressive alignment in an efficient way. The program contains a threshold parameter on which the size of the network depends. The larger the threshold parameter and thus the network, the deeper the search in the alignment space for better scored alignments.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We implemented the program in the Java programming language, and tested it on the BAliBASE database. Reticular Alignment can outperform ClustalW even if a very simple scoring scheme (BLOSUM62 and affine gap penalty) is implemented and merely the threshold value is increased. However, this set-up is not sufficient for outperforming other cutting-edge alignment methods. On the other hand, the reticular alignment search strategy together with sophisticated scoring schemes (for example, differentiating gap penalties for hydrophobic and hydrophylic amino acids) overcome FSA and in some accuracy measurement, even MAFFT. The program is available from <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/phylogeny-cafe.elte.hu\/RetAlign\/\" ext-link-type=\"uri\">http:\/\/phylogeny-cafe.elte.hu\/RetAlign\/<\/jats:ext-link>\n            <\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Reticular alignment is an efficient search strategy for finding accurate multiple alignments. The highest accuracy achieved when this searching strategy is combined with sophisticated scoring schemes.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-11-570","type":"journal-article","created":{"date-parts":[[2010,11,23]],"date-time":"2010-11-23T19:14:20Z","timestamp":1290539660000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Reticular alignment: A progressive corner-cutting method for multiple sequence alignment"],"prefix":"10.1186","volume":"11","author":[{"given":"Adrienn","family":"Szab\u00f3","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1d\u00e1m","family":"Nov\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istv\u00e1n","family":"Mikl\u00f3s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jotun","family":"Hein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,11,23]]},"reference":[{"key":"4153_CR1","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. Cambridge University Press; 1997."},{"issue":"3","key":"4153_CR2","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 1970, 48(3):443\u201353. 10.1016\/0022-2836(70)90057-4","journal-title":"J Mol Biol"},{"key":"4153_CR3","first-page":"253","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D Sankoff","year":"1983","unstructured":"Sankoff D, Cedergren RJ: Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, Massachusetts; 1983:253\u2013263. chap. Simultaneous comparison of three or more sequences related by a tree chap. Simultaneous comparison of three or more sequences related by a tree"},{"issue":"4","key":"4153_CR4","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L Wang","year":"1994","unstructured":"Wang L, Jiang T: On the complexity of multiple sequence alignment. J Comp Biol 1994, 1(4):337\u2013348. 10.1089\/cmb.1994.1.337","journal-title":"J Comp Biol"},{"key":"4153_CR5","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 alignment. Nucleic Acids Research 1984, 12: 175\u2013180. 10.1093\/nar\/12.1Part1.175","journal-title":"Nucleic Acids Research"},{"key":"4153_CR6","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E Ukkonnen","year":"1985","unstructured":"Ukkonnen E: Algorithms for approximate string matching. Inform Control 1985, 64: 100\u2013118. 10.1016\/S0019-9958(85)80046-2","journal-title":"Inform Control"},{"key":"4153_CR7","first-page":"1","volume":"7","author":"J Spouge","year":"1991","unstructured":"Spouge J: Fast optimal alignment. CABIOS 1991, 7: 1\u20137.","journal-title":"CABIOS"},{"key":"4153_CR8","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/jmbi.2000.4061","volume":"302","author":"J Hein","year":"2000","unstructured":"Hein J, Wiuf C, Knudsen B, Moller MB, Wibling G: Statistical alignment: computational properties, homology testing and goodness-of-fit. J Mol Biol 2000, 302: 265\u2013279. 10.1006\/jmbi.2000.4061","journal-title":"J Mol Biol"},{"issue":"6","key":"4153_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0020-0190(90)90035-V","volume":"35","author":"S Wu","year":"1990","unstructured":"Wu S, Manber U, Myers G, Miller W: An O(NP) sequence comparison algorithm. Information Processing Letters 1990, 35(6):317\u2013323. 10.1016\/0020-0190(90)90035-V","journal-title":"Information Processing Letters"},{"key":"4153_CR10","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo H, Lipman D: The multiple sequence alignment problem in biology. SIAM Journal of Applied Mathematics 1988, 48: 1073\u20131082. 10.1137\/0148063","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"4153_CR11","doi-asserted-by":"publisher","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"D Lipman","year":"1989","unstructured":"Lipman D, Altschul S, Kececioglu J: A tool for multiple sequence alignment. PNAS 1989, 86: 4412\u20134415. 10.1073\/pnas.86.12.4412","journal-title":"PNAS"},{"issue":"3","key":"4153_CR12","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","volume":"2","author":"S Gupta","year":"1995","unstructured":"Gupta S, Kececioglu J, Sch\u00e4ffer A: Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment. J Comp Biol 1995, 2(3):459\u2013472. 10.1089\/cmb.1995.2.459","journal-title":"J Comp Biol"},{"issue":"2","key":"4153_CR13","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF02257378","volume":"20","author":"P Hogeweg","year":"1984","unstructured":"Hogeweg P, Hesper B: The alignment of sets of sequences and the construction of phyletic trees: An integrated method. J Mol Evol 1984, 20(2):175\u2013186. 10.1007\/BF02257378","journal-title":"J Mol Evol"},{"key":"4153_CR14","doi-asserted-by":"crossref","unstructured":"Feng DF, Doolittle RF: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J Mol Evol 1987, (25):351\u2013360. 10.1007\/BF02603120","DOI":"10.1007\/BF02603120"},{"key":"4153_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0378-1119(88)90330-7","volume":"73","author":"D Higgins","year":"1988","unstructured":"Higgins D, Sharp P: CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene 1988, 73: 237\u201344. 10.1016\/0378-1119(88)90330-7","journal-title":"Gene"},{"key":"4153_CR16","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"J Thompson","year":"1994","unstructured":"Thompson J, Higgins D, Gibson T: ClustalW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucl Acids Res 1994, 22: 4673\u20134690. 10.1093\/nar\/22.22.4673","journal-title":"Nucl Acids Res"},{"key":"4153_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins D, Heringa J: T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol 2000, 302: 205\u201317. 10.1006\/jmbi.2000.4042","journal-title":"J Mol Biol"},{"issue":"14","key":"4153_CR18","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1093\/nar\/gkf436","volume":"30","author":"K Katoh","year":"2002","unstructured":"Katoh K, Misawa K, Kuma Ki, Miyata T: MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucl Acids Res 2002, 30(14):3059\u20133066. 10.1093\/nar\/gkf436","journal-title":"Nucl Acids Res"},{"issue":"16","key":"4153_CR19","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1093\/bioinformatics\/btl175","volume":"22","author":"MA Suchard","year":"2006","unstructured":"Suchard MA, Redelings BD: BAli-Phy: Simultaneous Bayesian inference of alignment and phylogeny. Bioinformatics 2006, 22(16):2047\u20132048. 10.1093\/bioinformatics\/btl175","journal-title":"Bioinformatics"},{"issue":"20","key":"4153_CR20","doi-asserted-by":"publisher","first-page":"2403","DOI":"10.1093\/bioinformatics\/btn457","volume":"24","author":"A Nov\u00e1k","year":"2008","unstructured":"Nov\u00e1k A, Mikl\u00f3s I, Lyngs\u00f8 R, Hein J: StatAlign: An Extendable Software Package for Joint Bayesian Estimation of Alignments and Evolutionary Trees. Bioinformatics 2008, 24(20):2403\u20132404. 10.1093\/bioinformatics\/btn457","journal-title":"Bioinformatics"},{"key":"4153_CR21","doi-asserted-by":"publisher","first-page":"e1000392","DOI":"10.1371\/journal.pcbi.1000392","volume":"5","author":"R Bradley","year":"2009","unstructured":"Bradley R, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L: Fast Statistical Alignment. PLoS Computational Biology 2009, 5: e1000392. 10.1371\/journal.pcbi.1000392","journal-title":"PLoS Computational Biology"},{"key":"4153_CR22","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1093\/bioinformatics\/14.1.25","volume":"14","author":"J Zhu","year":"1998","unstructured":"Zhu J, Liu J, Lawrence C: Bayesian adaptive sequence alignment algorithms. Bioinformatics 1998, 14: 25\u201339. 10.1093\/bioinformatics\/14.1.25","journal-title":"Bioinformatics"},{"key":"4153_CR23","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/prot.20527","volume":"61","author":"J Thompson","year":"2005","unstructured":"Thompson J, Koehl P, Ripp R, O P: BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. Proteins 2005, 61: 127\u2013136. 10.1002\/prot.20527","journal-title":"Proteins"},{"key":"4153_CR24","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0025-5564(85)90096-3","volume":"77","author":"MS Waterman","year":"1985","unstructured":"Waterman MS, Byers TH: A dynamic programming algorithm to find all solutions in the neighborhood of the optimum. Math Biosci 1985, 77: 179\u2013188. 10.1016\/0025-5564(85)90096-3","journal-title":"Math Biosci"},{"issue":"4","key":"4153_CR25","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol 1987, 4(4):406\u2013425.","journal-title":"Mol Biol Evol"},{"issue":"6","key":"4153_CR26","first-page":"729","volume":"5","author":"J Studier","year":"1988","unstructured":"Studier J, Keppler K: A note on the Neighbor-Joining algorithm of Saitou and Nei. Mol Biol Evol 1988, 5(6):729\u2013731.","journal-title":"Mol Biol Evol"},{"issue":"6","key":"4153_CR27","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS: A linear space algorithm for computing maximal common subsequences. Commun ACM 1975, 18(6):341\u2013343. 10.1145\/360825.360861","journal-title":"Commun ACM"},{"key":"4153_CR28","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-44888-8_19","volume":"2676","author":"B Ma","year":"2003","unstructured":"Ma B, Wang Z, Zhang K: Alignment between Two Multiple Alignments. Lecture Notes in Computer Science 2003, 2676: 254\u2013265. full_text","journal-title":"Lecture Notes in Computer Science"},{"issue":"22","key":"4153_CR29","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: Amino acid substitution matrices from protein blocks. Proc Natl Acad Sci USA 1992, 89(22):10915\u201310919. 10.1073\/pnas.89.22.10915","journal-title":"Proc Natl Acad Sci USA"},{"key":"4153_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis. Probabilistic models of proteins and nucleic acids","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological sequence analysis. Probabilistic models of proteins and nucleic acids. Cambridge University Press; 1998."},{"key":"4153_CR31","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1093\/bioinformatics\/14.5.401","volume":"14","author":"C Tarnas","year":"1998","unstructured":"Tarnas C, Hughey R: Reduced space hidden Markov model training. Bioinformatics 1998, 14: 401\u2013406. 10.1093\/bioinformatics\/14.5.401","journal-title":"Bioinformatics"},{"key":"4153_CR32","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/11732990_37","volume":"3909","author":"J Kececioglu","year":"2006","unstructured":"Kececioglu J, Kim E: Simple and Fast Inverse Alignment. Lecture Notes in Computer Science 2006, 3909: 441\u2013455. full_text","journal-title":"Lecture Notes in Computer Science"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-570.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-11-570\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-570.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T12:10:58Z","timestamp":1630498258000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-11-570"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,23]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["4153"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-11-570","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,23]]},"assertion":[{"value":"20 June 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"570"}}