On almost Monge all scores matrices. (English) Zbl 1410.68416
Summary: 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.
MSC:
| 68W32 | Algorithms on strings |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W40 | Analysis of algorithms |
Keywords:
sequence alignment; longest common subsequences; DIST matrices; Monge matrices; all-path score computations; multiple-source shortest-pathsSoftware:
PROSITEReferences:
| [1] | 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) · Zbl 0642.68078 · doi:10.1007/BF01840359 |
| [2] | 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) · Zbl 1138.68064 · doi:10.1016/j.dam.2007.05.056 |
| [3] | 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) · Zbl 0711.68055 · doi:10.1137/0219066 |
| [4] | Apostolico, A.: String editing and longest common subsequences. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 361-398. Springer (1997) |
| [5] | 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) |
| [6] | Benson, G.: A space efficient algorithm for finding the best nonoverlapping alignment score. Theor. Comput. Sci. 145(1&2), 357-369 (1995) · Zbl 0873.68041 · doi:10.1016/0304-3975(95)92848-R |
| [7] | 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) |
| [8] | Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of monge properties in optimization. Discrete Appl. Math. 70(2), 95-161 (1996) · Zbl 0856.90091 · doi:10.1016/0166-218X(95)00103-X |
| [9] | Cabello, S., Chambers, E.W., Erickson, J.: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542-1571 (2013) · Zbl 1276.05031 · doi:10.1137/120864271 |
| [10] | Comet, J.-P., Henry, J.: Pairwise sequence alignment using a prosite pattern-derived similarity score. Comput. Chem. 26(5), 421-436 (2002) · doi:10.1016/S0097-8485(02)00005-0 |
| [11] | 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) · Zbl 1253.74047 · doi:10.1137/S0097539702402007 |
| [12] | 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) · Zbl 1293.90057 |
| [13] | Evans, P.A.: Algorithms and Complexity for Annotated Sequence Analysis. Ph.D. thesis, Citeseer (1999) |
| [14] | 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) · Zbl 1236.68308 |
| [15] | 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) · Zbl 1143.90366 · doi:10.1137/050638308 |
| [16] | 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) · doi:10.1093/nar/gkj063 |
| [17] | 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) · Zbl 1122.68442 |
| [18] | Kannan, S., Myers, E.W.: An algorithm for locating nonoverlapping regions of maximum alignment score. SIAM J. Comput. 25(3), 648-662 (1996) · Zbl 0855.68021 · doi:10.1137/S0097539794262677 |
| [19] | Kent, C., Landau, G.M., Ziv-Ukelson, M.: On the complexity of sparse exon assembly. J. Comput. Biol. 13(5), 1013-1027 (2006) · Zbl 1130.92300 · doi:10.1089/cmb.2006.13.1013 |
| [20] | Kim, S.-R., Park, K.: A dynamic edit distance table. J. Discrete Algorithms 2(2), 303-312 (2004) · Zbl 1118.68757 · doi:10.1016/S1570-8667(03)00082-0 |
| [21] | 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) · Zbl 1297.05059 |
| [22] | Krusche, P., Tiskin, A.: String comparison by transposition networks, In: Proceedings of the of London Algorithmics, Workshop, pp. 184-204 (2008) · Zbl 1216.68356 |
| [23] | 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) · Zbl 1172.68674 |
| [24] | Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput. 27(2), 557-582 (1998) · Zbl 0907.68075 · doi:10.1137/S0097539794264810 |
| [25] | 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) · Zbl 1165.90668 · doi:10.1016/j.jcss.2007.03.004 |
| [26] | Landau, G.M., Schieber, B., Ziv-Ukelson, M.: Sparse LCS common substring alignment. Inf. Process. Lett. 88(6), 259-270 (2003) · Zbl 1178.68186 · doi:10.1016/j.ipl.2003.09.006 |
| [27] | Landau, G.M., Schmidt, J.P., Sokol, D.: An algorithm for approximate tandem repeats. J. Comput. Biol. 8(1), 1-18 (2001) · doi:10.1089/106652701300099038 |
| [28] | Landau, G.M., Ziv-Ukelson, M.: On the common substring alignment problem. J. Algorithms 41(2), 338-359 (2001) · Zbl 1017.68039 · doi:10.1006/jagm.2001.1191 |
| [29] | Matarazzo, U., Tsur, D., Ziv-Ukelson, M.: Efficient all path score computations on grid graphs. Theor. Comput. Sci. 525, 138-149 (2014) · Zbl 1282.68204 · doi:10.1016/j.tcs.2013.07.018 |
| [30] | Mozes, S., Tsur, D., Weimann, O., Ziv-Ukelson, M.: Fast algorithms for computing tree lcs. Theor. Comput. Sci. 410(43), 4303-4314 (2009) · Zbl 1187.68684 · doi:10.1016/j.tcs.2009.07.011 |
| [31] | 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) · Zbl 0743.68079 · doi:10.1016/0020-0190(91)90118-2 |
| [32] | Sakai, Y.: An almost quadratic time algorithm for sparse spliced alignment. Theory Comput. Syst. 48(1), 189-210 (2011) · Zbl 1209.68703 · doi:10.1007/s00224-009-9239-x |
| [33] | 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) · Zbl 0907.68076 · doi:10.1137/S0097539795288489 |
| [34] | Tiskin, A.: Semi-local longest common subsequences in subquadratic time. J. Discrete Algorithms 6(4), 570-581 (2008) · Zbl 1154.68543 · doi:10.1016/j.jda.2008.07.001 |
| [35] | Tiskin, A.: Semi-local string comparison: algorithmic techniques and applications. Math. Comput. Sci. 1(4), 571-603 (2008) · Zbl 1158.68054 · doi:10.1007/s11786-007-0033-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
