PMC:1698483 / 37506-40661 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1698483","sourcedb":"PMC","sourceid":"1698483","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1698483","text":"The pos-list for X[l, u]Y can be computed in time linear in the lengths of P (X, Si) and P (Y, Si), i.e., the complexity of a positional join is O(|P (X, Si)| + |P (Y, Si)|). In essence, each time we advance x ∈ P (X, Si), we check if there exists a y ∈ P (Y, Si) that satisfies the given gap constraint. Instead of searching for the matching y from the beginning of the pos-list each time, we search from the last position used to compare with x. This results in fast positional joins. For example, during the positional join for the motif A[0,1]T in S4, with l = 0 and u = 1, we scan the pos-lists of A and T for S4 in Table 2, i.e. P (X, S4) = {2, 3, 7} and P (Y, S4) = {1, 8, 12, 13, 14}. Initially, x = 2 and y = 1. This gives d = 1 - 2 - 1 = - 2 \u003cl, thus we advance y to 8. Next, d = 8 - 2 - 1 = 5 \u003e u, thus we advance x to 3. Then, d = 8 - 3 - 1 = 4 \u003e u, thus we advance x to 7. Next, d = 8 - 7 - 1 = 0 ∈ [l, u], so we store x = 7 in P (A[0, 1]T, S4). We would advance x but since we have already reached the end of P (A, S4), the positional join stops. Thus the final pos-list of A[0,1]T in S4 is: P (A[0, 1]T, S4) = {7}. After we obtain the pos-list of ℳ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFZestaaa@3790@ in each Si for 1 ≤ i ≤ n, we can combine them together to obtain the pos-list of ℳ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFZestaaa@3790@ in S MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFse=uaaa@3845@. For example, the full pos-list of A[0,1]T for S MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFse=uaaa@3845@ is: {2, 2, 6, 15, 3, 2, 2, 10, 4, 1, 7}. Thus the support of A[0,1]T is 3. Note here for each non-empty pos-list, we insert its sequence identifier and length before it. The pseudo-code for the positional joins for a given sequence Si ∈ S MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFse=uaaa@3845@ is shown in Figure 1. The full pos-list is obtained by concatenating the pos-lists from each sequence Si.","tracks":[]}