Document Open Access Logo

On Almost Monge All Scores Matrices

Authors Amir Carmel, Dekel Tsur, Michal Ziv-Ukelson

PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.17.pdf
  • Filesize: 0.53 MB
  • 12 pages

Document Identifiers

Author Details

Amir Carmel
Dekel Tsur
Michal Ziv-Ukelson

Cite As Get BibTex

Amir Carmel, Dekel Tsur, and Michal Ziv-Ukelson. On Almost Monge All Scores Matrices. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CPM.2016.17

Abstract

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 the 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 give an O(r(nm + n2)) time algorithm for constructing the all scores matrix of an m × n grid graph with r bridges.

Subject Classification

Keywords
  • Sequence alignment
  • longest common subsequences
  • DIST matrices
  • Monge matrices
  • all path score computations.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. C. E. R. Alves, E. N. Cáceres, and S. W. Song. An all-substrings common subsequence algorithm. Discrete Applied Mathematics, 156(7):1025-1035, 2008. Google Scholar
  2. A. Apostolico, M. J. Atallah, L. L. Larmore, and S. McFaddin. Efficient parallel algorithms for string editing and related problems. SIAM J. on Computing, 19(5):968-988, 1990. Google Scholar
  3. A. N. Arslan. Sequence alignment guided by common motifs. In Proceedings of the fourth Biotechnology and Bioinformatics Symposium, page 30. University of Colorado at Colorado Springs, 2007. Google Scholar
  4. A. N. Arslan. Sequence alignment guided by common motifs described by context free grammars. In Biotechnology and Bioinformatics Symp. (BIOT'07), 2007. Google Scholar
  5. G. Benson. A space efficient algorithm for finding the best nonoverlapping alignment score. Theoretical Computer Science, 145(1&2):357-369, 1995. Google Scholar
  6. H. L. Bodlaender, M. R. Fellows, and P. A. Evans. Finite-state computability of annotations of strings and trees. In Combinatorial Pattern Matching, pages 384-391. Springer, 1996. Google Scholar
  7. S. Cabello, E. W. Chambers, and J. Erickson. Multiple-source shortest paths in embedded graphs. SIAM J. on Computing, 42(4):1542-1571, 2013. Google Scholar
  8. J.-P. Comet and J. Henry. Pairwise sequence alignment using a prosite pattern-derived similarity score. Computers &chemistry, 26(5):421-436, 2002. Google Scholar
  9. M. Crochemore, G. M. Landau, and M. Ziv-Ukelson. A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. SIAM J. on Computing, 32(5):1654-1673, 2003. Google Scholar
  10. D. Eisenstat and P. N. Klein. Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In Proc. 45th ACM Symposium on Theory Of Computing (STOC), pages 735-744, 2013. Google Scholar
  11. P. A. Evans. Algorithms and complexity for annotated sequence analysis. PhD thesis, Citeseer, 1999. Google Scholar
  12. D. Hermelin, G. M. Landau, S. Landau, and O. Weimann. A unified algorithm for accelerating edit-distance computation via text-compression. In Proc. 26th Symposium on Theoretical Aspects of Computer Science (STACS), pages 529-540, 2009. Google Scholar
  13. N. Hulo, A. Bairoch, V. Bulliard, L. Cerutti, E. De Castro, P. S. Langendijk-Genevaux, M. Pagni, and C. Sigrist. The prosite database. Nucleic acids research, 34(suppl 1):D227-D230, 2006. Google Scholar
  14. Y. Ishida, S. Inenaga, A. Shinohara, and M. Takeda. Fully incremental LCS computation. In Proc. 15th Symp. on Fundamentals of Computation Theory (FCT), pages 563-574, 2005. Google Scholar
  15. S. Kannan and E. W. Myers. An algorithm for locating nonoverlapping regions of maximum alignment score. SIAM J. on Computing, 25(3):648-662, 1996. Google Scholar
  16. C. Kent, G. M. Landau, and M. Ziv-Ukelson. On the complexity of sparse exon assembly. Journal of Computational Biology, 13(5):1013-1027, 2006. Google Scholar
  17. S.-R. Kim and K. Park. A dynamic edit distance table. J. of Discrete Algorithms, 2(2):303-312, 2004. Google Scholar
  18. P. N. Klein. Multiple-source shortest paths in planar graphs. In Proc. 16th Symposium on Discrete Algorithms (SODA), volume 5, pages 146-155, 2005. Google Scholar
  19. P. Krusche and A. Tiskin. String comparison by transposition networks. In Proc. of London Algorithmics Workshop, pages 184-204, 2008. Google Scholar
  20. P. Krusche and A. Tiskin. New algorithms for efficient parallel string comparison. In Proc. 22nd Symposium on Parallel Algorithms and Architectures (SPAA), pages 209-216, 2010. Google Scholar
  21. G. M. Landau, E. W. Myers, and J. P. Schmidt. Incremental string comparison. SIAM J. on Computing, 27(2):557-582, 1998. Google Scholar
  22. G. M. Landau, E. W. Myers, and M. Ziv-Ukelson. Two algorithms for LCS consecutive suffix alignment. J. of Computer and System Sciences, 73(7):1095-1117, 2007. Google Scholar
  23. G. M. Landau, B. Schieber, and M. Ziv-Ukelson. Sparse LCS common substring alignment. Information Processing Letters, 88(6):259-270, 2003. Google Scholar
  24. G. M. Landau, J. P. Schmidt, and D. Sokol. An algorithm for approximate tandem repeats. J. of Computational Biology, 8(1):1-18, 2001. Google Scholar
  25. G. M. Landau and M. Ziv-Ukelson. On the common substring alignment problem. J. of Algorithms, 41(2):338-359, 2001. Google Scholar
  26. U. Matarazzo, D. Tsur, and M. Ziv-Ukelson. Efficient all path score computations on grid graphs. Theoretical Computer Science, 525:138-149, 2014. Google Scholar
  27. S. Mozes, D. Tsur, O. Weimann, and M. Ziv-Ukelson. Fast algorithms for computing tree lcs. Theoretical Computer Science, 410(43):4303-4314, 2009. Google Scholar
  28. Y. Sakai. An almost quadratic time algorithm for sparse spliced alignment. Theory of Computing Systems, pages 1-22, 2009. Google Scholar
  29. J. P. Schmidt. All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. of Computing, 27(4):972-992, 1998. Google Scholar
  30. A. Tiskin. Semi-local string comparison: algorithmic techniques and applications. arXiv:0707.3619v16. Google Scholar
  31. A. Tiskin. Semi-local longest common subsequences in subquadratic time. J. Discrete Algorithms, 6(4):570-581, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact