@inbook{a8b87698567f4d3f83fe48926d06a80a,

title = "Maximal Motif discovery in a sliding window",

abstract = "Motifs are relatively short sequences that are biologically significant, and their discovery in molecular sequences is a well-researched subject. A don{\textquoteright}t care is a special letter that matches every letter in the alphabet. Formally, a motif is a sequence of letters of the alphabet and don{\textquoteright}t care letters. A motif (Formula presented) that occurs at least k times in a sequence is maximal if it cannot be extended (to the left or right) nor can it be specialised (that is, its d{\textquoteright}≤d don{\textquoteright}t cares cannot be replaced with letters from the alphabet) without reducing its number of occurrences. Here we present a new dynamic data structure, and the first on-line algorithm, to discover all maximal motifs in a sliding window of length l on a sequence x of length n in (Formula presented) time, where w is the size of the machine word and DIFFi i-1 is the symmetric difference of the sets of occurrences of maximal motifs at x[i-l..i-1] and at x[i-l+1..i].",

keywords = "Genome analysis, Motif discovery, Sequence motifs",

author = "Iliopoulos, {Costas S.} and Manal Mohamed and Pissis, {Solon P.} and Fatima Vayani",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-00479-8_16",

language = "English",

isbn = "9783030004781",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "191--205",

editor = "Travis Gagie and Alistair Moffat and Gonzalo Navarro and Ernesto Cuadros-Vargas",

booktitle = "String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings",

address = "Germany",

note = "25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018",

}