@inproceedings{bb67375468ca46c7ac567c004eceae91,
title = "A linear-time algorithm for the 1-mismatch problem",
abstract = "For sequence alignments (which can be viewed simply as rectangular arrays of characters), a frequent need is to identify regions, each consisting of a run of consecutive columns, that have some particular property. The 1-mismatch problem is to locate all maximal regions in a given alignment for which there exists a (not necessarily unique) “center” sequence such that inside the region alignment rows are within Hamming distance 1 from the center. We first describe some properties of these regions and their centers, and then use these properties to construct an algorithm that for a dxn alignment runs in time θ(nd) and extra space θ(d) (beyond that needed for the storage of the alignment itself).",
author = "Nikola Stojanovic and Piotr Berman and Deborah Gumucio and Ross Hardison and Webb Miller",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 5th International Workshop on Algorithms and Data Structures, WADS 1997 ; Conference date: 06-08-1997 Through 08-08-1997",
year = "1997",
doi = "10.1007/3-540-63307-3_53",
language = "English (US)",
isbn = "3540633073",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "126--135",
editor = "Frank Dehne and Jorg-Rudiger Sack and Andrew Rau-Chaplin and Roberto Tamassia",
booktitle = "Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings",
address = "Germany",
}