PMC:1687185 / 34730-44064 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1687185","sourcedb":"PMC","sourceid":"1687185","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1687185","text":"6 Experimental Results\nExperiments were performed on both synthetic data and real data. Two different methods were used in the global phase: random start and random projection. The main purpose of this paper is not to demonstrate that our algorithm can outperform the existing motif finding algorithms. Rather, the main work here focuses on improving the results that are obtained from other efficient algorithms. We have chosen to demonstrate the performance of our algorithm on the results obtained from the random projection method which is a powerful global method that has outperformed other traditional motif finding approaches like MEME, Gibbs sampling, WINNOWER, SP-STAR, etc. [1]. Since the comparison was already published, we mainly focus on the performance improvements of our algorithm as compared to the random projection algorithm. For the random start experiment, a total of N random numbers between 1 and (t - l + 1) corresponding to initial set of alignments are generated. We then proceeded to evaluate our Exit-point methodology from these alignments.\n\n6.1 Synthetic Datasets\nThe synthetic datasets were generated by implanting some motif instances into t = 20 sequences each of length ti = 600. Let m correspond to one full random projection + EM cycle. We have set m = 1 to demonstrate the efficiency of our approach. We compared the performance coefficient (PC) which gives a measure of the average performance of our implementation compared to that of Random Projection. The PC is given by :\nP C = | K ∩ P | | K ∪ P |       ( 9 ) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGqbaucqWGdbWqcqGH9aqpdaWcaaqaamaaemaabaGaem4saSKaeyykICSaemiuaafacaGLhWUaayjcSdaabaWaaqWaaeaacqWGlbWscqGHQicYcqWGqbauaiaawEa7caGLiWoaaaGaaCzcaiaaxMaadaqadaqaaiabiMda5aGaayjkaiaawMcaaaaa@41D9@\nwhere K is the set of the residue positions of the planted motif instances, and P is the corresponding set of positions predicted by the algorithm. Table 3 gives an overview of the performance of our method compared to the random projection algorithm on the (l, d) motif problem for different l and d values.\nTable 3 Improvements in the Performance Coefficient.\nMotif (l, d) PC obtained using Random Projection PC obtained using Exit-point method\n(11,2) 20 20\n(15,4) 14.875 17\n(20,6) 12.667 18\nThe results of performance coefficient with m = 1 on synthetically generated sequences. The IC scores are not normalized and the perfect score is 20 since there are 20 sequences. Our results show that by branching out and discovering multiple local optimal solutions, higher m values are not needed. A higher m value corresponds to more computational time because projecting the l-mers into k-sized buckets is a time consuming task. Using our approach, we can replace the need for randomly projecting l-mers repeatedly in an effort to converge to a global optimum by deterministically and systematically searching the solution space modeled by our dynamical system and improving the quality of the existing solutions. We can see that for higher length motifs, the improvements are more significant. Fig. 4 shows the Tier-1 solutions obtained from a given consensus pattern. Since the exit points are being used instead of saddle points, our method might sometimes find the same local optimal solution obtained before. As seen from the figure, the Tier-1 solutions can differ from the original pattern by more than just one nucleotide position. Also, the function value at the exit points is much higher than the original value.\nAs opposed to stochastic processes like mutations in genetic algorithms, our approach reduces the stochastic nature and obtains the nearby local optimal solutions systematically. Fig. 5 shows the performance of the Exit-point approach on synthetic data for different (l, d) motifs. The average scores of the ten best solutions obtained from random starts and their corresponding improvements in Tier-1 and Tier-2 are reported. One can see that the improvements become more prominent as the length of the motif is increased. Table 4 shows the best and worst of these top ten random starts along with the consensus pattern and the alignment scores.\nFigure 5 The average scores with the corresponding first tier and second tier improvements on synthetic data using the random starts with Exit-point approach with different (l, d) motifs.\nTable 4 Improvements in the Information Content Scores.\n(l, d) Initial Pattern Score First Tier Pattern Score Second Tier Pattern Score\n(11,2) AACGGTCGCAG 125.1 CCCGGTCGCTG 147.1 CCCGGGAGCTG 153.3\n(11,2) ATACCAGTTAC 145.7 ATACCAGTTTC 151.3 ATACCAGGGTC 153.6\n(13,3) CTACGGTCGTCTT 142.6 CCACGGTTGTCTC 157.8 CCTCGGGTTTGTC 158.7\n(13,3) GACGCTAGGGGGT 158.3 GAGGCTGGGCAGT 161.7 GACCTTGGGTATT 165.8\n(15,4) CCGAAAAGAGTCCGA 147.5 CCGCAATGACTGGGT 169.1 CCGAAAGGACTGCGT 176.2\n(15,4) TGGGTGATGCCTATG 164.6 TGGGTGATGCCTATG 166.7 TGAGAGATGCCTATG 170.4\n(17,5) TTGTAGCAAAGGCTAAA 143.3 CAGTAGCAAAGACTACC 173.3 CAGTAGCAAAGACTTCC 175.8\n(17,5) ATCGCGAAAGGTTGTGG 174.1 ATCGCGAAAGGATGTGG 176.7 ATTGCGAAAGAATGTGG 178.3\n(20,6) CTGGTGATTGAGATCATCAT 165.9 CAGATGGTTGAGATCACCTT 186.9 CATTTAGCTGAGTTCACCTT 194.9\n(20,6) GGTCACTTAGTGGCGCCATG 216.3 GGTCACTTAGTGGCGCCATG 218.8 CGTCACTTAGTCGCGCCATG 219.7\nThe consensus patterns and their corresponding scores of the original local optimal solution obtained from multiple random starts on the synthetic data. The best first tier and second tier optimal patterns and their corresponding scores are also reported. With a few modifications, more experiments were conducted using the Random Projection method. The Random Projection method will eliminate non-promising regions in the search space and gives a number of promising sets of initial patterns. EM refinement is applied to only the promising initial patterns. Due to the robustness of the results, the Exit-point method is employed only on the top five local optima. The Exit-point method is again repeated on the top scoring first tier solutions to arrive at the second tier solutions. Fig. 6 shows the average alignment scores of the best random projection alignments and their corresponding improvements in tier-1 and tier-2 are reported. In general, the improvement in the first tier solutions are more significant than the improvements in the second tier solutions.\nFigure 6 The average scores with the corresponding first tier and second tier improvements on synthetic data using the Random Projection with Exit-point approach with different (l, d) motifs.\n\n6.2 Real Datasets\nTable 5 shows the results of the Exit-point methodology on real biological sequences. We have chosen l = 20 and d = 2. 't' indicates the number of sequences in the real data. For the biological samples taken from [1,12], the value m once again is the average number of random projection + EM cycles required to discover the motif. All other parameter values (like projection size k = 7 and threshold s = 4) are chosen to be the same as those used in the Random projection paper [1]. All of the motifs were recovered with m = 1 using the Exit-point strategy. The Random Projection algorithm alone needed multiple cycles (m = 8 in some cases and m = 15 in others) in order to retrieve the correct motif. This elucidates the fact that global methods can only be used to a certain extent and should be combined with refined local heuristics in order to obtain better efficiency. Since the random projection algorithm has outperformed other prominent motif finding algorithms like SP-STAR, WINNOWER, Gibbs sampling etc., we did not repeat the same experiments that were conducted in [1]. Running one cycle of random projection + EM is much more expensive computationally. The main advantage of our strategy comes from the deterministic nature of our algorithm in refining motifs.\nTable 5 Results on real datasets. Results of Exit-point method on biological samples. The real motifs were obtained in all the six cases using the Exit-point framework.\nSequence Sample Size t Best (20,2) Motif Reference Motif\nE. coli CRP 1890 18 TGTGAAATAGATCACATTTT TGTGANNNNGNTCACA\npreproinsulin 7689 4 GGAAATTGCAGCCTCAGCCC CCTCAGCCC\nDHFR 800 4 CTGCAATTTCGCGCCAAACT ATTTCNNGCCA\nmetallothionein 6823 4 CCCTCTGCGCCCGGACCGGT TGCRCYCGG\nc-fos 3695 5 CCATATTAGGACATCTGCGT CCATATTAGAGACTCT\nyeast ECB 5000 5 GTATTTCCCGTTTAGGAAAA TTTCCCNNTNAGGAAA Let the cost of applying EM algorithm for a given bucket be f and let the average number of buckets for a given projection be b. Then the running time of the Exit-point method will be O(cbf) where c is a constant that is linear in l-the length of the motif. If there were m projections, then cost of the random projection algorithm using restarts will be O(mbf). The two main advantages of using Exit-point strategy compared to random projection algorithm are :\n• It avoids multiple random projections which often provide similar optimal motifs.\n• It provides multiple optimal solutions in a promising region of a given bucket as opposed to a single solution provided by random projection algorithm.","divisions":[{"label":"title","span":{"begin":0,"end":22}},{"label":"p","span":{"begin":23,"end":1071}},{"label":"sec","span":{"begin":1073,"end":6767}},{"label":"title","span":{"begin":1073,"end":1095}},{"label":"p","span":{"begin":1096,"end":1515}},{"label":"p","span":{"begin":1516,"end":1998}},{"label":"p","span":{"begin":1999,"end":2307}},{"label":"table-wrap","span":{"begin":2308,"end":2680}},{"label":"label","span":{"begin":2308,"end":2315}},{"label":"caption","span":{"begin":2317,"end":2361}},{"label":"p","span":{"begin":2317,"end":2361}},{"label":"table","span":{"begin":2362,"end":2501}},{"label":"tr","span":{"begin":2362,"end":2448}},{"label":"td","span":{"begin":2362,"end":2374}},{"label":"td","span":{"begin":2376,"end":2411}},{"label":"td","span":{"begin":2413,"end":2448}},{"label":"tr","span":{"begin":2449,"end":2463}},{"label":"td","span":{"begin":2449,"end":2455}},{"label":"td","span":{"begin":2457,"end":2459}},{"label":"td","span":{"begin":2461,"end":2463}},{"label":"tr","span":{"begin":2464,"end":2482}},{"label":"td","span":{"begin":2464,"end":2470}},{"label":"td","span":{"begin":2472,"end":2478}},{"label":"td","span":{"begin":2480,"end":2482}},{"label":"tr","span":{"begin":2483,"end":2501}},{"label":"td","span":{"begin":2483,"end":2489}},{"label":"td","span":{"begin":2491,"end":2497}},{"label":"td","span":{"begin":2499,"end":2501}},{"label":"table-wrap-foot","span":{"begin":2502,"end":2680}},{"label":"p","span":{"begin":2502,"end":2680}},{"label":"p","span":{"begin":2681,"end":3729}},{"label":"p","span":{"begin":3730,"end":4376}},{"label":"figure","span":{"begin":4377,"end":4565}},{"label":"label","span":{"begin":4377,"end":4385}},{"label":"caption","span":{"begin":4387,"end":4565}},{"label":"p","span":{"begin":4387,"end":4565}},{"label":"table-wrap","span":{"begin":4566,"end":5760}},{"label":"label","span":{"begin":4566,"end":4573}},{"label":"caption","span":{"begin":4575,"end":4622}},{"label":"p","span":{"begin":4575,"end":4622}},{"label":"table","span":{"begin":4623,"end":5504}},{"label":"tr","span":{"begin":4623,"end":4708}},{"label":"td","span":{"begin":4623,"end":4629}},{"label":"td","span":{"begin":4631,"end":4646}},{"label":"td","span":{"begin":4648,"end":4653}},{"label":"td","span":{"begin":4655,"end":4673}},{"label":"td","span":{"begin":4675,"end":4680}},{"label":"td","span":{"begin":4682,"end":4701}},{"label":"td","span":{"begin":4703,"end":4708}},{"label":"tr","span":{"begin":4709,"end":4775}},{"label":"td","span":{"begin":4709,"end":4715}},{"label":"td","span":{"begin":4717,"end":4728}},{"label":"td","span":{"begin":4730,"end":4735}},{"label":"td","span":{"begin":4737,"end":4748}},{"label":"td","span":{"begin":4750,"end":4755}},{"label":"td","span":{"begin":4757,"end":4768}},{"label":"td","span":{"begin":4770,"end":4775}},{"label":"tr","span":{"begin":4776,"end":4842}},{"label":"td","span":{"begin":4776,"end":4782}},{"label":"td","span":{"begin":4784,"end":4795}},{"label":"td","span":{"begin":4797,"end":4802}},{"label":"td","span":{"begin":4804,"end":4815}},{"label":"td","span":{"begin":4817,"end":4822}},{"label":"td","span":{"begin":4824,"end":4835}},{"label":"td","span":{"begin":4837,"end":4842}},{"label":"tr","span":{"begin":4843,"end":4915}},{"label":"td","span":{"begin":4843,"end":4849}},{"label":"td","span":{"begin":4851,"end":4864}},{"label":"td","span":{"begin":4866,"end":4871}},{"label":"td","span":{"begin":4873,"end":4886}},{"label":"td","span":{"begin":4888,"end":4893}},{"label":"td","span":{"begin":4895,"end":4908}},{"label":"td","span":{"begin":4910,"end":4915}},{"label":"tr","span":{"begin":4916,"end":4988}},{"label":"td","span":{"begin":4916,"end":4922}},{"label":"td","span":{"begin":4924,"end":4937}},{"label":"td","span":{"begin":4939,"end":4944}},{"label":"td","span":{"begin":4946,"end":4959}},{"label":"td","span":{"begin":4961,"end":4966}},{"label":"td","span":{"begin":4968,"end":4981}},{"label":"td","span":{"begin":4983,"end":4988}},{"label":"tr","span":{"begin":4989,"end":5067}},{"label":"td","span":{"begin":4989,"end":4995}},{"label":"td","span":{"begin":4997,"end":5012}},{"label":"td","span":{"begin":5014,"end":5019}},{"label":"td","span":{"begin":5021,"end":5036}},{"label":"td","span":{"begin":5038,"end":5043}},{"label":"td","span":{"begin":5045,"end":5060}},{"label":"td","span":{"begin":5062,"end":5067}},{"label":"tr","span":{"begin":5068,"end":5146}},{"label":"td","span":{"begin":5068,"end":5074}},{"label":"td","span":{"begin":5076,"end":5091}},{"label":"td","span":{"begin":5093,"end":5098}},{"label":"td","span":{"begin":5100,"end":5115}},{"label":"td","span":{"begin":5117,"end":5122}},{"label":"td","span":{"begin":5124,"end":5139}},{"label":"td","span":{"begin":5141,"end":5146}},{"label":"tr","span":{"begin":5147,"end":5231}},{"label":"td","span":{"begin":5147,"end":5153}},{"label":"td","span":{"begin":5155,"end":5172}},{"label":"td","span":{"begin":5174,"end":5179}},{"label":"td","span":{"begin":5181,"end":5198}},{"label":"td","span":{"begin":5200,"end":5205}},{"label":"td","span":{"begin":5207,"end":5224}},{"label":"td","span":{"begin":5226,"end":5231}},{"label":"tr","span":{"begin":5232,"end":5316}},{"label":"td","span":{"begin":5232,"end":5238}},{"label":"td","span":{"begin":5240,"end":5257}},{"label":"td","span":{"begin":5259,"end":5264}},{"label":"td","span":{"begin":5266,"end":5283}},{"label":"td","span":{"begin":5285,"end":5290}},{"label":"td","span":{"begin":5292,"end":5309}},{"label":"td","span":{"begin":5311,"end":5316}},{"label":"tr","span":{"begin":5317,"end":5410}},{"label":"td","span":{"begin":5317,"end":5323}},{"label":"td","span":{"begin":5325,"end":5345}},{"label":"td","span":{"begin":5347,"end":5352}},{"label":"td","span":{"begin":5354,"end":5374}},{"label":"td","span":{"begin":5376,"end":5381}},{"label":"td","span":{"begin":5383,"end":5403}},{"label":"td","span":{"begin":5405,"end":5410}},{"label":"tr","span":{"begin":5411,"end":5504}},{"label":"td","span":{"begin":5411,"end":5417}},{"label":"td","span":{"begin":5419,"end":5439}},{"label":"td","span":{"begin":5441,"end":5446}},{"label":"td","span":{"begin":5448,"end":5468}},{"label":"td","span":{"begin":5470,"end":5475}},{"label":"td","span":{"begin":5477,"end":5497}},{"label":"td","span":{"begin":5499,"end":5504}},{"label":"table-wrap-foot","span":{"begin":5505,"end":5760}},{"label":"p","span":{"begin":5505,"end":5760}},{"label":"p","span":{"begin":5761,"end":6574}},{"label":"figure","span":{"begin":6575,"end":6767}},{"label":"label","span":{"begin":6575,"end":6583}},{"label":"caption","span":{"begin":6585,"end":6767}},{"label":"p","span":{"begin":6585,"end":6767}},{"label":"title","span":{"begin":6769,"end":6786}},{"label":"p","span":{"begin":6787,"end":8061}},{"label":"table-wrap","span":{"begin":8062,"end":8634}},{"label":"label","span":{"begin":8062,"end":8069}},{"label":"caption","span":{"begin":8071,"end":8231}},{"label":"p","span":{"begin":8071,"end":8231}},{"label":"table","span":{"begin":8232,"end":8634}},{"label":"tr","span":{"begin":8232,"end":8296}},{"label":"td","span":{"begin":8232,"end":8241}},{"label":"td","span":{"begin":8242,"end":8254}},{"label":"td","span":{"begin":8256,"end":8258}},{"label":"td","span":{"begin":8260,"end":8278}},{"label":"td","span":{"begin":8280,"end":8296}},{"label":"tr","span":{"begin":8297,"end":8358}},{"label":"td","span":{"begin":8297,"end":8308}},{"label":"td","span":{"begin":8310,"end":8314}},{"label":"td","span":{"begin":8316,"end":8318}},{"label":"td","span":{"begin":8320,"end":8340}},{"label":"td","span":{"begin":8342,"end":8358}},{"label":"tr","span":{"begin":8359,"end":8414}},{"label":"td","span":{"begin":8359,"end":8372}},{"label":"td","span":{"begin":8374,"end":8378}},{"label":"td","span":{"begin":8380,"end":8381}},{"label":"td","span":{"begin":8383,"end":8403}},{"label":"td","span":{"begin":8405,"end":8414}},{"label":"tr","span":{"begin":8415,"end":8462}},{"label":"td","span":{"begin":8415,"end":8419}},{"label":"td","span":{"begin":8421,"end":8424}},{"label":"td","span":{"begin":8426,"end":8427}},{"label":"td","span":{"begin":8429,"end":8449}},{"label":"td","span":{"begin":8451,"end":8462}},{"label":"tr","span":{"begin":8463,"end":8520}},{"label":"td","span":{"begin":8463,"end":8478}},{"label":"td","span":{"begin":8480,"end":8484}},{"label":"td","span":{"begin":8486,"end":8487}},{"label":"td","span":{"begin":8489,"end":8509}},{"label":"td","span":{"begin":8511,"end":8520}},{"label":"tr","span":{"begin":8521,"end":8575}},{"label":"td","span":{"begin":8521,"end":8526}},{"label":"td","span":{"begin":8528,"end":8532}},{"label":"td","span":{"begin":8534,"end":8535}},{"label":"td","span":{"begin":8537,"end":8557}},{"label":"td","span":{"begin":8559,"end":8575}},{"label":"tr","span":{"begin":8576,"end":8634}},{"label":"td","span":{"begin":8576,"end":8585}},{"label":"td","span":{"begin":8587,"end":8591}},{"label":"td","span":{"begin":8593,"end":8594}},{"label":"td","span":{"begin":8596,"end":8616}},{"label":"td","span":{"begin":8618,"end":8634}},{"label":"p","span":{"begin":8635,"end":9096}},{"label":"p","span":{"begin":9097,"end":9180}}],"tracks":[]}