On Almost Monge All Scores Matrices
Tóm tắt
The all scores matrix of a grid graph is a matrix containing the optimal scores of paths from every vertex on the first row of the graph to every vertex on its last row. This matrix is commonly used to solve diverse string comparison problems. All scores matrices have the Monge property, and this was exploited by previous works that used all scores matrices for solving various problems. In this paper, we study an extension of grid graphs that contain an additional set of edges, called bridges. Our main result is to show several properties of the all scores matrices of such graphs. We also apply these properties to obtain an
$$O(r(nm+n^2))$$
time algorithm for constructing the all scores matrix of an
$$m\times n$$
grid graph with r bridges and bounded integer weights.
Tài liệu tham khảo
Aggarwal, A., Klawe, M.M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(1–4), 195–208 (1987)
Alves, C.E.R., Cáceres, E.N., Song, S.W.: An all-substrings common subsequence algorithm. Discrete Appl. Math. 156(7), 1025–1035 (2008)
Apostolico, A., Atallah, M.J., Larmore, L.L., McFaddin, S.: Efficient parallel algorithms for string editing and related problems. SIAM J. Comput. 19(5), 968–988 (1990)
Apostolico, A.: String editing and longest common subsequences. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 361–398. Springer (1997)
Arslan, A.N.: Sequence alignment guided by common motifs described by context free grammars. In: Biotechnology and Bioinformatics Symposium (BIOT-2007). Colorado Springs, CO (2007)
Benson, G.: A space efficient algorithm for finding the best nonoverlapping alignment score. Theor. Comput. Sci. 145(1&2), 357–369 (1995)
Bodlaender, H.L., Fellows, M.R., Evans, P.A.: Finite-state computability of annotations of strings and trees. In: Proceedings of the 7th Symposium on Combinatorial Pattern Matching (CPM), pp. 384–391. Springer (1996)
Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of monge properties in optimization. Discrete Appl. Math. 70(2), 95–161 (1996)
Cabello, S., Chambers, E.W., Erickson, J.: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542–1571 (2013)
Comet, J.-P., Henry, J.: Pairwise sequence alignment using a prosite pattern-derived similarity score. Comput. Chem. 26(5), 421–436 (2002)
Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. SIAM J. Comput. 32(5), 1654–1673 (2003)
Eisenstat, D., Klein, P.N.: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In: Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), pp. 735–744 (2013)
Evans, P.A.: Algorithms and Complexity for Annotated Sequence Analysis. Ph.D. thesis, Citeseer (1999)
Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A unified algorithm for accelerating edit-distance computation via text-compression. In: Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 529–540 (2009)
Hou, X., Prékopa, A.: Monge property and bounding multivariate probability distribution functions with given marginals and covariances. SIAM J. Optim. 18(1), 138–155 (2007)
Hulo, N., Bairoch, A., Bulliard, V., Cerutti, L., De Castro, E., Langendijk-Genevaux, P.S., Pagni, M., Sigrist, C.: The prosite database. Nucleic Acids Res. 34(suppl 1), D227–D230 (2006)
Ishida, Y., Inenaga, S., Shinohara, A., Takeda, M.: Fully incremental LCS computation. In: Proceedings of the 15th Symposium on Fundamentals of Computation Theory (FCT), pp. 563–574 (2005)
Kannan, S., Myers, E.W.: An algorithm for locating nonoverlapping regions of maximum alignment score. SIAM J. Comput. 25(3), 648–662 (1996)
Kent, C., Landau, G.M., Ziv-Ukelson, M.: On the complexity of sparse exon assembly. J. Comput. Biol. 13(5), 1013–1027 (2006)
Kim, S.-R., Park, K.: A dynamic edit distance table. J. Discrete Algorithms 2(2), 303–312 (2004)
Klein, P.N.: Multiple-source shortest paths in planar graphs. In: Proceedings of the 16th Symposium on Discrete Algorithms (SODA), vol. 5, pp. 146–155 (2005)
Krusche, P., Tiskin, A.: String comparison by transposition networks, In: Proceedings of the of London Algorithmics, Workshop, pp. 184–204 (2008)
Krusche, P., Tiskin, A.: New algorithms for efficient parallel string comparison. In: Proceedings of the 22nd Symposium on Parallel Algorithms and Architectures (SPAA), pp. 209–216 (2010)
Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput. 27(2), 557–582 (1998)
Landau, G.M., Myers, E.W., Ziv-Ukelson, M.: Two algorithms for LCS consecutive suffix alignment. J. Comput. Syst. Sci. 73(7), 1095–1117 (2007)
Landau, G.M., Schieber, B., Ziv-Ukelson, M.: Sparse LCS common substring alignment. Inf. Process. Lett. 88(6), 259–270 (2003)
Landau, G.M., Schmidt, J.P., Sokol, D.: An algorithm for approximate tandem repeats. J. Comput. Biol. 8(1), 1–18 (2001)
Landau, G.M., Ziv-Ukelson, M.: On the common substring alignment problem. J. Algorithms 41(2), 338–359 (2001)
Matarazzo, U., Tsur, D., Ziv-Ukelson, M.: Efficient all path score computations on grid graphs. Theor. Comput. Sci. 525, 138–149 (2014)
Mozes, S., Tsur, D., Weimann, O., Ziv-Ukelson, M.: Fast algorithms for computing tree lcs. Theor. Comput. Sci. 410(43), 4303–4314 (2009)
Park, J.K.: A special case of the n-vertex traveling-salesman problem that can be solved in o (n) time. Inf. Process. Lett. 40(5), 247–254 (1991)
Sakai, Y.: An almost quadratic time algorithm for sparse spliced alignment. Theory Comput. Syst. 48(1), 189–210 (2011)
Schmidt, J.P.: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. Comput. 27(4), 972–992 (1998)
Tiskin, A.: Semi-local longest common subsequences in subquadratic time. J. Discrete Algorithms 6(4), 570–581 (2008)
Tiskin, A.: Semi-local string comparison: algorithmic techniques and applications. Math. Comput. Sci. 1(4), 571–603 (2008)