{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T11:31:21Z","timestamp":1652700681882},"reference-count":86,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T00:00:00Z","timestamp":1521417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100013296","name":"Max Planck Institute for Mathematics in the Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013296","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s11786-018-0338-4","type":"journal-article","created":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T11:18:15Z","timestamp":1521458295000},"page":"207-234","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Partially Local Multi-way Alignments"],"prefix":"10.1007","volume":"12","author":[{"given":"Nancy","family":"Retzlaff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,19]]},"reference":[{"key":"338_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 59\u201378. IEEE (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"338_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Hansen, T.D., Williams, V.V., Williams, R.: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC \u201916), New York, NY, pp. 375\u2013388 (2016)","DOI":"10.1145\/2897518.2897653"},{"key":"338_CR3","doi-asserted-by":"publisher","first-page":"W3","DOI":"10.1093\/nar\/gkt283","volume":"41","author":"L Al Ait","year":"2013","unstructured":"Al Ait, L., Yamak, Z., Morgenstern, B., Morgenstern, B.: DIALIGN at GOBICS\u2014multiple sequence alignment using various sources of external information. Nucleic Acids Res. 41, W3\u2013W7 (2013)","journal-title":"Nucleic Acids Res."},{"key":"338_CR4","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/s13015-017-0113-0","volume":"12","author":"M Al Arab","year":"2017","unstructured":"Al Arab, M., Bernt, M., zu Siederdissen, C.H., Tout, K.: Partially local three-way alignments and the sequence signatures of mitochondrial genome rearrangements. Alg. Mol. Biol. 12, 22 (2017)","journal-title":"Alg. Mol. Biol."},{"key":"338_CR5","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0022-5193(89)80196-1","volume":"138","author":"SF Altschul","year":"1989","unstructured":"Altschul, S.F.: Gap costs for multiple sequence alignment. J. Theor. Biol. 138, 297\u2013309 (1989)","journal-title":"J. Theor. Biol."},{"key":"338_CR6","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215, 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"338_CR7","doi-asserted-by":"publisher","first-page":"3240","DOI":"10.1093\/bioinformatics\/bts622","volume":"28","author":"C Angerm\u00fcller","year":"2012","unstructured":"Angerm\u00fcller, C., Biegert, A., S\u00f6ding, J.: Discriminative modelling of context-specific amino acid substitution probabilities. Bioinformatics 28, 3240\u20133247 (2012)","journal-title":"Bioinformatics"},{"key":"338_CR8","first-page":"1209","volume":"11","author":"V Arlazarov","year":"1970","unstructured":"Arlazarov, V., Dinic, E., Kronrod, M., Faradzev, I.: On economical construction of the transitive closure of a directed graph. Dokl. Akad. Nauk. 11, 1209\u20131210 (1970)","journal-title":"Dokl. Akad. Nauk."},{"issue":"157","key":"338_CR9","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.biosystems.2017.03.003","volume":"156","author":"S Baichoo","year":"2017","unstructured":"Baichoo, S., Ouzounis, C.A.: Computational complexity of algorithms for sequence comparison, short-read assembly and genome alignment. Biosystems 156(157), 72\u201385 (2017)","journal-title":"Biosystems"},{"key":"338_CR10","doi-asserted-by":"publisher","first-page":"W369","DOI":"10.1093\/nar\/gkl198","volume":"34","author":"TL Bailey","year":"2006","unstructured":"Bailey, T.L., Williams, N., Misleh, C., Wilfred, W.L.: MEME: discovering and analyzing DNA and protein sequence motifs. Nucleic Acids Res. 34, W369\u2013W373 (2006)","journal-title":"Nucleic Acids Res."},{"key":"338_CR11","doi-asserted-by":"crossref","unstructured":"Bhattacharya, T., Retzlaff, N., Blasi, D., Croft, W., Cysouw, M., Hruschka, D., Maddieson, I., M\u00fcller, L., Smith, E., Stadler, P.F., Starostin, G., Youn, H.: Studying language evolution in the age of big data. J. Lang. Evol. (2018)","DOI":"10.1093\/jole\/lzy004"},{"key":"338_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1146\/annurev.genom.8.080706.092300","volume":"8","author":"M Blanchette","year":"2007","unstructured":"Blanchette, M.: Computation and analysis of genomic multi-sequence alignments. Annu. Rev. Genomics Hum. Genet. 8, 193\u2013213 (2007)","journal-title":"Annu. Rev. Genomics Hum. Genet."},{"key":"338_CR13","doi-asserted-by":"publisher","first-page":"3840","DOI":"10.1093\/nar\/gkg606","volume":"31","author":"M Blanchette","year":"2003","unstructured":"Blanchette, M., Tompa, M.: FootPrinter: a program designed for phylogenetic footprinting. Nucleic Acids Res. 31, 3840\u20133842 (2003)","journal-title":"Nucleic Acids Res."},{"key":"338_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1089\/10665270252935421","volume":"9","author":"M Blanchette","year":"2002","unstructured":"Blanchette, M., Schwikowski, B., Tompa, M.: Algorithms for phylogenetic footprinting. J. Comput. Biol. 9, 211\u2013223 (2002)","journal-title":"J. Comput. Biol."},{"key":"338_CR15","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(99)00324-2","volume":"259","author":"P Bonizzoni","year":"2001","unstructured":"Bonizzoni, P., Della Vedova, G.: The complexity of multiple sequence alignment with SP-score that is a metric. Theor. Comput. Sci. 259, 63\u201379 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"338_CR16","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1186\/1471-2105-4-66","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 Bioinform. 4, 66 (2003)","journal-title":"BMC Bioinform."},{"key":"338_CR17","first-page":"44","volume-title":"Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology (ISMB \u201996)","author":"P Bucher","year":"1996","unstructured":"Bucher, P., Hoffmann, K.: A sequence similarity search algorithm based on a probabilistic interpretation of an alignment scoring system. In: States, D.J., Agarwal, P., Gaasterland, T., Hunter, L., Smith, R.F. (eds.) Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology (ISMB \u201996), pp. 44\u201350. AAAI Press, Menlo Park, CA (1996)"},{"key":"338_CR18","doi-asserted-by":"publisher","first-page":"6886","DOI":"10.1093\/nar\/gkr335","volume":"39","author":"G Bussotti","year":"2011","unstructured":"Bussotti, G., Raineri, E., Erb, I., Zytnicki, M., Wilm, A., Beaudoing, E., Bucher, P., Notredame, C.: BlastR-fast and accurate database searches for non-coding RNAs. Nucleic Acids Res. 39, 6886\u20136895 (2011)","journal-title":"Nucleic Acids Res."},{"key":"338_CR19","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 J. Appl. Math. 48, 1073\u20131082 (1988)","journal-title":"SIAM J. Appl. Math."},{"key":"338_CR20","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.ygeno.2017.06.007","volume":"109","author":"B Chowdhurya","year":"2017","unstructured":"Chowdhurya, B., Garaib, G.: A review on multiple sequence alignment from the perspective of genetic algorithm. Genomics 109, 419\u2013431 (2017)","journal-title":"Genomics"},{"key":"338_CR21","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1186\/1471-2105-13-117","volume":"13","author":"PW Collingridge","year":"2012","unstructured":"Collingridge, P.W., Kelly, S.: Mergealign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments. BMC Bioinform. 13, 117 (2012)","journal-title":"BMC Bioinform."},{"key":"338_CR22","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1093\/bioinformatics\/btq082","volume":"26","author":"E Corel","year":"2010","unstructured":"Corel, E., Pitschi, F., Morgenstern, B.: A min-cut algorithm for the consistency problem in multiple sequence alignment. Bioinformatics 26, 1015\u20131021 (2010)","journal-title":"Bioinformatics"},{"key":"338_CR23","doi-asserted-by":"crossref","unstructured":"Cysouw, M., Jung, H.: Cognate identification and alignment using practical orthographies. In: Proceedings of Ninth Meeting of the ACL Special Interest Group in Computational Morphology and Phonology, pp. 109\u2013116. Association for Computational Linguistics (2007)","DOI":"10.3115\/1626516.1626530"},{"key":"338_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1089\/106652701300312931","volume":"8","author":"TG Dewey","year":"2001","unstructured":"Dewey, T.G.: A sequence alignment algorithm with an arbitrary gap penalty function. J. Comput. Biol. 8, 177\u2013190 (2001)","journal-title":"J. Comput. Biol."},{"key":"338_CR25","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"RD Dowell","year":"2004","unstructured":"Dowell, R.D., Eddy, S.R.: Evaluation of several lightweight stochastic context free grammars for RNA secondary structure prediction. BMC Bioinform. 5, 71 (2004)","journal-title":"BMC Bioinform."},{"key":"338_CR26","doi-asserted-by":"publisher","first-page":"e1000069","DOI":"10.1371\/journal.pcbi.1000069","volume":"4","author":"SR Eddy","year":"2008","unstructured":"Eddy, S.R.: A probabilistic model of local sequence alignment that simplifies statistical significance estimation. PLoS Comput. Biol. 4, e1000069 (2008)","journal-title":"PLoS Comput. Biol."},{"key":"338_CR27","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1089\/cmb.2006.13.1323","volume":"13","author":"I Elias","year":"2006","unstructured":"Elias, I.: Settling the intractability of multiple alignment. J. Comput. Biol. 13, 1323\u20131339 (2006)","journal-title":"J. Comput. Biol."},{"key":"338_CR28","doi-asserted-by":"publisher","first-page":"3169","DOI":"10.1093\/bioinformatics\/bts605","volume":"28","author":"NA Fonseca","year":"2012","unstructured":"Fonseca, N.A., Rung, J., Brazma, A., Marioni, J.C.: Tools for mapping high-throughput sequencing data. Bioinformatics 28, 3169\u20133177 (2012)","journal-title":"Bioinformatics"},{"key":"338_CR29","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/3-540-45123-4_6","volume-title":"Combinatorial Pattern Matching CPM 2000","author":"R Giegerich","year":"2002","unstructured":"Giegerich, R.: Explaining and controlling ambiguity in dynamic programming. In: Giancarlo, R., Sankoff, D. (eds.) Combinatorial Pattern Matching CPM 2000, vol. 1848, pp. 46\u201359. Springer, Berlin (2002)"},{"key":"338_CR30","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R Giegerich","year":"2004","unstructured":"Giegerich, R., Meyer, C., Steffen, P.: A discipline of dynamic programming over sequence data. Sci. Comput. Prog. 51, 215\u2013263 (2004)","journal-title":"Sci. Comput. Prog."},{"key":"338_CR31","doi-asserted-by":"publisher","first-page":"705708","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh, O.: An improved algorithm for matching biological sequences. J. Mol. Biol. 162, 705708 (1982)","journal-title":"J. Mol. Biol."},{"key":"338_CR32","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0022-5193(86)80112-6","volume":"121","author":"O Gotoh","year":"1986","unstructured":"Gotoh, O.: Alignment of three biological sequences with an efficient traceback procedure. J. Theor. Biol. 121, 327\u2013337 (1986)","journal-title":"J. Theor. Biol."},{"key":"338_CR33","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","volume":"2","author":"SK Gupta","year":"1995","unstructured":"Gupta, S.K., Kececioglu, J.D., Sch\u00e4ffer, A.A.: Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment. J. Comput. Biol. 2, 459\u2013472 (1995)","journal-title":"J. Comput. Biol."},{"key":"338_CR34","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1093\/nar\/gkn1084","volume":"37","author":"J Hertel","year":"2009","unstructured":"Hertel, J., de Jong, D., Marz, M., Rose, D., Tafer, H., Tanzer, A., Schierwater, B., Stadler, P.F.: Non-coding RNA annotation of the genome of Trichoplax adhaerens. Nucleic Acids Res. 37, 1602\u20131615 (2009)","journal-title":"Nucleic Acids Res."},{"key":"338_CR35","first-page":"13","volume":"11","author":"M Hirosawa","year":"1995","unstructured":"Hirosawa, M., Totoki, Y., Hoshida, M., Ishikawa, M.: Comprehensive study on iterative algorithms of multiple sequence alignment. Comput. Appl. Biosci. 11, 13\u201318 (1995)","journal-title":"Comput. Appl. Biosci."},{"key":"338_CR36","doi-asserted-by":"publisher","first-page":"R34","DOI":"10.1186\/gb-2014-15-2-r34","volume":"15","author":"S Hoffmann","year":"2014","unstructured":"Hoffmann, S., Otto, C., Doose, G., Tanzer, A., Langenberger, D., Christ, S., Kunz, M., Holdt, L.M., Teupser, D., Hackerm\u00fcller, J., Stadler, P.F.: A multi-split mapping algorithm for circular RNA, splicing, trans-splicing, and fusion detection. Genome Biol. 15, R34 (2014)","journal-title":"Genome Biol."},{"key":"338_CR37","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. 20, 175\u2013186 (1984)","journal-title":"J. Mol. Evol."},{"key":"338_CR38","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1101\/gr.229202","volume":"12","author":"W James Kent","year":"2002","unstructured":"James Kent, W.: BLAT\u2014the BLAST-like alignment tool. Genome Res. 12, 656\u2013664 (2002)","journal-title":"Genome Res."},{"key":"338_CR39","volume-title":"An Introduction to Bioinformatics","author":"NC Jones","year":"2004","unstructured":"Jones, N.C., Pevzner, P.A.: An Introduction to Bioinformatics. MIT Press, Cambride (2004). Problem 6.22"},{"key":"338_CR40","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1089\/106652701753307511","volume":"8","author":"W Just","year":"2001","unstructured":"Just, W.: Computational complexity of multiple sequence alignment with SP-score. J. Comput. Biol. 8, 615\u2013623 (2001)","journal-title":"J. Comput. Biol."},{"key":"338_CR41","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-1-62703-646-7_8","volume":"1079","author":"K Katoh","year":"2014","unstructured":"Katoh, K., Standley, D.M.: MAFFT: iterative refinement and additional methods. Methods Mol. Biol. 1079, 131\u2013146 (2014)","journal-title":"Methods Mol. Biol."},{"key":"338_CR42","doi-asserted-by":"crossref","unstructured":"Kececioglu, J.D.: The maximum weight trace problem in multiple sequence alignment. In: Proceedings of the 4th Symposium on Combinatorial Pattern Matching, volume 684 of Lecture Notes Computer Science, pp. 106\u2013119. Springer, Berlin (1993)","DOI":"10.1007\/BFb0029800"},{"key":"338_CR43","doi-asserted-by":"crossref","unstructured":"Kececioglu, J., Starrett, D.: Aligning alignments exactly. In: Bourne, P.E., Gusfield, D. (eds.) Proceedings of the 8th ACM Conference on Research in Computational Molecular Biology (RECOMB), pp. 85\u201396. ACM, New York, NY (2004)","DOI":"10.1145\/974614.974626"},{"key":"338_CR44","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0166-218X(00)00194-3","volume":"104","author":"JD Kececioglu","year":"2000","unstructured":"Kececioglu, J.D., Lenhof, H.-P., Mehlhorn, K., Mutzel, P., Reinert, K., Vingron, M.: A polyhedral approach to sequence alignment problems. Discrete Appl. Math. 104, 143\u2013186 (2000)","journal-title":"Discrete Appl. Math."},{"key":"338_CR45","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1142\/S0219720004000831","volume":"2","author":"AS Konagurthu","year":"2004","unstructured":"Konagurthu, A.S., Whisstock, J., Stuckey, P.J.: Progressive multiple alignment using sequence triplet optimization and three-residue exchange costs. J. Bioinform. Comput. Biol. 2, 719\u2013745 (2004)","journal-title":"J. Bioinform. Comput. Biol."},{"key":"338_CR46","unstructured":"Kondrak, G.: A new algorithm for the alignment of phonetic sequences. In: Proceedings of NAACL 2000 1st Meeting of the North American Chapter of the Association for Computational Linguistics, pp. 288\u2013295. Morgan Kaufmann Publishers, San Francisco, CA (2000)"},{"key":"338_CR47","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1023\/A:1025071200644","volume":"37","author":"G Kondrak","year":"2003","unstructured":"Kondrak, G.: Phonetic alignment and similarity. Comput. Humanit. 37, 273\u2013291 (2003)","journal-title":"Comput. Humanit."},{"key":"338_CR48","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1186\/1471-2105-8-254","volume":"8","author":"M Kruspe","year":"2007","unstructured":"Kruspe, M., Stadler, P.F.: Progressive multiple sequence alignments from triplets. BMC Bioinform. 8, 254 (2007). https:\/\/doi.org\/10.1186\/1471-2105-8-254","journal-title":"BMC Bioinform."},{"key":"338_CR49","doi-asserted-by":"publisher","first-page":"e0170046","DOI":"10.1371\/journal.pone.0170046","volume":"12","author":"J-M List","year":"2017","unstructured":"List, J.-M., Greenhill, S.J., Gray, R.D.: The potential of automatic word comparison for historical linguistics. PLoS ONE 12, e0170046 (2017)","journal-title":"PLoS ONE"},{"key":"338_CR50","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1093\/bioinformatics\/15.11.947","volume":"15","author":"AV Lukashin","year":"1999","unstructured":"Lukashin, A.V., Rosa, J.J.: Local multiple sequence alignment using dead-end elimination. Bioinformatics 15, 947\u2013953 (1999)","journal-title":"Bioinformatics"},{"key":"338_CR51","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0304-3975(02)00439-5","volume":"296","author":"B Manthey","year":"2003","unstructured":"Manthey, B.: Non-approximability of weighted multiple sequence alignment. Theor. Comput. Sci. 296, 179\u2013192 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"338_CR52","doi-asserted-by":"publisher","first-page":"2507","DOI":"10.1101\/gr.1602203","volume":"13","author":"EH Margulies","year":"2003","unstructured":"Margulies, E.H., Blanchette, M., Haussler, D., Green, E.D.: Identification and characterization of multi-species conserved sequences. Genome Res. 13, 2507\u20132518 (2003)","journal-title":"Genome Res."},{"key":"338_CR53","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1093\/bioinformatics\/btu697","volume":"31","author":"A Meier","year":"2015","unstructured":"Meier, A., S\u00f6ding, J.: Context similarity scoring improves protein sequence alignments in the midnight zone. Bioinformatics 31, 674\u2013681 (2015)","journal-title":"Bioinformatics"},{"key":"338_CR54","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1093\/protein\/8.10.999","volume":"8","author":"S Miyazawa","year":"1994","unstructured":"Miyazawa, S.: A reliable sequence alignment method based on probabilities of residue correspondences. Protein Eng. 8, 999\u20131009 (1994)","journal-title":"Protein Eng."},{"issue":"3","key":"338_CR55","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 14(3), 290\u2013294 (1998)","journal-title":"Bioinformatics"},{"key":"338_CR56","unstructured":"Morgenstern, B., Stoye, J., Dress, A.W.M.: Consistent equivalence relations: a set-theoretical framework for multiple sequence alignments. Technical report, University of Bielefeld, FSPM (1999)"},{"key":"338_CR57","first-page":"S153-S118","volume":"60","author":"U M\u00fcckstein","year":"2002","unstructured":"M\u00fcckstein, U., Hofacker, I.L., Stadler, P.F.: Stochastic pairwise alignments. Bioinformatics 60, S153-S118 (2002)","journal-title":"Bioinformatics"},{"key":"338_CR58","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB 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. J. Mol. Biol. 48, 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"key":"338_CR59","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 multiple sequence alignments. J. Mol. Biol. 302, 205\u2013217 (2000)","journal-title":"J. Mol. Biol."},{"key":"338_CR60","doi-asserted-by":"crossref","unstructured":"Otto, W., Stadler, P.F., Prohaska, S.J.: Phylogenetic footprinting and consistent sets of local alignments. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011, volume 6661 of Lecture Notes in Computer Science, pp. 118\u2013131. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-21458-5_12"},{"key":"338_CR61","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., Miller, W.: Mulan: multiple-sequence local alignment and visualization for studying function and evolution. Genome Res. 15, 184\u2013194 (2005)","journal-title":"Genome Res."},{"key":"338_CR62","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/pro.5560010203","volume":"1","author":"J Overington","year":"1992","unstructured":"Overington, J., Donnelly, D., Johnson, M.S., \u0160ali, A., Blundell, T.L.: Environment-specific amino acid substitution tables: tertiary templates and prediction of protein folds. Protein Sci. 1, 216\u2013226 (1992)","journal-title":"Protein Sci."},{"key":"338_CR63","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/j.ympev.2003.08.009","volume":"31","author":"S Prohaska","year":"2004","unstructured":"Prohaska, S., Fried, C., Flamm, C., Wagner, G., Stadler, P.F.: Surveying phylogenetic footprints in large gene clusters: applications to Hox cluster duplications. Mol. Phylogen. Evol. 31, 581\u2013604 (2004)","journal-title":"Mol. Phylogen. Evol."},{"key":"338_CR64","doi-asserted-by":"publisher","first-page":"R47","DOI":"10.1186\/gb-2010-11-5-r47","volume":"11","author":"K Pr\u00fcfer","year":"2010","unstructured":"Pr\u00fcfer, K., Stenzel, U., Hofreiter, M., P\u00e4\u00e4bo, S., Kelso, J., Green, R.E.: Computational challenges in the analysis of ancient DNA. Genome Biol. 11, R47 (2010)","journal-title":"Genome Biol."},{"key":"338_CR65","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1093\/bioinformatics\/btp131","volume":"25","author":"T Rausch","year":"2009","unstructured":"Rausch, T., Koren, S., Denisov, G., Weese, D., Emde, A.-K., D\u00f6ring, A., Reinert, K.: A consistency-based consensus algorithm for de novo and reference-guided sequence assembly of short reads. Bioinformatics 25, 1118\u20131124 (2009)","journal-title":"Bioinformatics"},{"key":"338_CR66","unstructured":"Retzlaff, N.: A two-step scoring model for computational phylolinguistics. In: de Haan, Ronald (ed.), Proceedings of the ESSLLI 2014 Student Session, pp. 196\u2013206. TU Wien, Vienna, A (2014). www.kr.tuwien.ac.at\/drm\/dehaan\/stus2014\/proceedings.pdf . Accessed 21 Feb 2018"},{"key":"338_CR67","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff, D.: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math. 45, 810\u2013825 (1985)","journal-title":"SIAM J. Appl. Math."},{"key":"338_CR68","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D Sankoff","year":"1983","unstructured":"Sankoff, D., Kruskal, J.B.: Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA (1983)"},{"key":"338_CR69","volume-title":"Introduction to Computational Molecular Biology","author":"JC Setubal","year":"1997","unstructured":"Setubal, J.C., Meidanis, J.: Introduction to Computational Molecular Biology. PWS Pub, Boston, MA (1997)"},{"key":"338_CR70","doi-asserted-by":"crossref","unstructured":"Shigemizu, D., Maruyama, O.: Searching for regulatory elements of alternative splicing events using phylogenetic footprinting. In: Jonassen, I., Kim, J. (eds.) 4th International Workshop on Algorithms in Bioinformatics, vol. 3240, pp. 147\u2013158. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-30219-3_13"},{"key":"338_CR71","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/pro.3290","volume":"27","author":"F Sievers","year":"2018","unstructured":"Sievers, F., Higgins, D.G.: Clustal Omega for making accurate alignments of many protein sequences. Protein Sci. 27, 135\u2013145 (2018)","journal-title":"Protein Sci."},{"key":"338_CR72","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. J. Mol. Biol. 147, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"338_CR73","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1163\/221058211X570358","volume":"1","author":"L Steiner","year":"2011","unstructured":"Steiner, L., Stadler, P.F., Cysouw, M.: A pipeline for computational historical linguistics. Lang. Dyn. Change 1, 89\u2013127 (2011)","journal-title":"Lang. Dyn. Change"},{"key":"338_CR74","doi-asserted-by":"publisher","first-page":"1498","DOI":"10.1093\/bioinformatics\/btp261","volume":"25","author":"Y Tabei","year":"2009","unstructured":"Tabei, Y., Asai, K.: A local multiple alignment method for detection of non-coding RNA sequences. Bioinformatics 25, 1498\u20131505 (2009)","journal-title":"Bioinformatics"},{"key":"338_CR75","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/prot.20527","volume":"61","author":"JD Thompson","year":"2005","unstructured":"Thompson, J.D., Koehl, P., Ripp, R., Poch, O.: BAliBASE 3.0: latestdevelopments of the multiple sequence alignment benchmark. Proteins 61, 127\u2013136 (2005)","journal-title":"Proteins"},{"key":"338_CR76","doi-asserted-by":"publisher","first-page":"e18093","DOI":"10.1371\/journal.pone.0018093","volume":"6","author":"JD Thompson","year":"2011","unstructured":"Thompson, J.D., Linard, B., Lecompte, O., Poch, O.: A comprehensive benchmark study of multiple sequence alignment methods: current challenges and future perspectives. PLoS ONE 6, e18093 (2011)","journal-title":"PLoS ONE"},{"key":"338_CR77","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. Comput. Biol. 1, 337\u2013348 (1994)","journal-title":"J. Comput. Biol."},{"key":"338_CR78","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0001-8708(76)90202-4","volume":"20","author":"MS Waterman","year":"1976","unstructured":"Waterman, M.S., Smith, T.F., Beyer, W.A.: Some biological sequence metrics. Adv. Math. 20, 367\u2013387 (1976)","journal-title":"Adv. Math."},{"key":"338_CR79","doi-asserted-by":"publisher","first-page":"i559","DOI":"10.1093\/bioinformatics\/btm226","volume":"23","author":"TJ Wheeler","year":"2007","unstructured":"Wheeler, T.J., Kececioglu, J.D.: Multiple alignment by aligning alignments. Bioinformatics 23, i559\u2013i568 (2007)","journal-title":"Bioinformatics"},{"key":"338_CR80","doi-asserted-by":"publisher","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","volume":"3","author":"S Will","year":"2007","unstructured":"Will, S., Missal, K., Hofacker, I.L., Stadler, P.F., Backofen, R.: Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering. PLoS Comput. Biol. 3, e65 (2007)","journal-title":"PLoS Comput. Biol."},{"key":"338_CR81","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1186\/1748-7188-8-14","volume":"8","author":"S Will","year":"2013","unstructured":"Will, S., Siebauer, M.F., Heyne, S., Engelhardt, J., Stadler, P.F., Reiche, K., Backofen, R.: LocARNAscan: Incorporating thermodynamic stability in sequence and structure-based RNA homology search. Alg. Mol. Biol. 8, 14 (2013)","journal-title":"Alg. Mol. Biol."},{"key":"338_CR82","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1186\/1471-2105-7-524","volume":"7","author":"S Yamada","year":"2006","unstructured":"Yamada, S., Gotoh, O., Yamana, H.: Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost. BMC Bioinform. 7, 524 (2006)","journal-title":"BMC Bioinform."},{"key":"338_CR83","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1089\/10665270152530845","volume":"8","author":"Y Yi-Kuo","year":"2001","unstructured":"Yi-Kuo, Y., Hwa, T.: Statistical significance of probabilistic sequence alignment and related local hidden markov models. J. Comput. Biol. 8, 249\u2013282 (2001)","journal-title":"J. Comput. Biol."},{"key":"338_CR84","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1186\/1475-4924-2-11","volume":"2","author":"Z Zhang","year":"2003","unstructured":"Zhang, Z., Gerstein, M.: Of mice and men: phylogenetic footprinting aids the discovery of regulatory elements. J. Biol. 2, 11 (2003)","journal-title":"J. Biol."},{"key":"338_CR85","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1109\/TCBB.2014.2326155","volume":"12","author":"CH Siederdissen zu","year":"2015","unstructured":"zu Siederdissen, C.H., Hofacker, I.L., Stadler, P.F.: Product grammars for alignment and folding. IEEE\/ACM Trans. Comput. Biol. Bioinform. 12, 507\u2013519 (2015)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"338_CR86","doi-asserted-by":"publisher","first-page":"19:S2","DOI":"10.1186\/1471-2105-16-S19-S2","volume":"16","author":"CH Siederdissen zu","year":"2015","unstructured":"zu Siederdissen, C.H., Prohaska, S.J., Stadler, P.F.: Algebraic dynamic programming over general data structures. BMC Bioinform. 16, 19:S2 (2015)","journal-title":"BMC Bioinform."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-018-0338-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-018-0338-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-018-0338-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T04:57:26Z","timestamp":1589864246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-018-0338-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,19]]},"references-count":86,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["338"],"URL":"https:\/\/doi.org\/10.1007\/s11786-018-0338-4","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,19]]},"assertion":[{"value":"9 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}