License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.17
URN: urn:nbn:de:0030-drops-60770
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6077/
Go to the corresponding LIPIcs Volume Portal

Carmel, Amir ; Tsur, Dekel ; Ziv-Ukelson, Michal

On Almost Monge All Scores Matrices

pdf-format:
LIPIcs-CPM-2016-17.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{carmel_et_al:LIPIcs:2016:6077,
  author =	{Amir Carmel and Dekel Tsur and Michal Ziv-Ukelson},
  title =	{{On Almost Monge All Scores Matrices}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Roberto Grossi and Moshe Lewenstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6077},
  URN =		{urn:nbn:de:0030-drops-60770},
  doi =		{10.4230/LIPIcs.CPM.2016.17},
  annote =	{Keywords: Sequence alignment, longest common subsequences, DIST matrices, Monge matrices, all path score computations.}
}

Keywords: Sequence alignment, longest common subsequences, DIST matrices, Monge matrices, all path score computations.
Collection: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Issue Date: 2016
Date of publication: 27.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI