PMC:1459173 / 16125-17719 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1459173","sourcedb":"PMC","sourceid":"1459173","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1459173","text":"Iteration phase\nLet B be the collection of cells. If m = Extract(B), then m ∈ B and there does not exist m' ∈ B such that m' ∗ m holds: m1 ∗ m2 if one of the following holds: (1) m1 has only solid characters and m2 has at least one non-solid character (2) m2 has the \"-\" character and m1 does not, and, (3) m1 and m2 have d1, d2 \u003e 0 dot characters respectively and d1 \u003cd2.\nFurther, m1 is ~-compatible with m2 if the last solid character of m1 is the same as the first solid character of m2. Further if m1 is ~-compatible with m2, then m = m1 ~ m2 is the concatenation of m1 and m2 with an overlap at the common end and start character and m = {(x, y)|(x, l) ∈ }. For example if m1 = ab and m2 = b.d then m1 is ~-compatible with m2 and m1 ~ m2 = ab.d. However, m2 is not ~-compatible with m1.\nNodeInconsistent(m) is a routine that checks if the new motif m is non-maximal w.r.t. earlier non-ancestral nodes by checking the location lists. The procedure is best described by the pseudocode shown in Table 1. Steps G:18–19 detect the suffix motifs of already detected maximal motifs. Result is the collection of all the maximal extensible patterns.\nA tight time complexity for the procedure is not easy to come by, however, if we consider M to be the number of extensible maximal motifs and S to be the size of the output – i.e. the sum of the sizes of the motifs and the sizes of the corresponding location lists – then the time taken by the algorithm is O(SM log M). In experiments of the kind described later in the paper, at 3 GHz clock, time ranged typically from few minutes to half an hour.","divisions":[{"label":"title","span":{"begin":0,"end":15}},{"label":"p","span":{"begin":16,"end":372}},{"label":"p","span":{"begin":373,"end":791}},{"label":"p","span":{"begin":792,"end":1145}}],"tracks":[]}