@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",

}