forked from nanoporetech/modkit
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathintro_find_motifs.html
More file actions
449 lines (406 loc) · 36.8 KB
/
Copy pathintro_find_motifs.html
File metadata and controls
449 lines (406 loc) · 36.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
<!DOCTYPE HTML>
<html lang="en" class="light sidebar-visible" dir="ltr">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Find highly modified motif sequences - Modkit</title>
<!-- Custom HTML head -->
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff">
<link rel="icon" href="favicon-de23e50b.svg">
<link rel="shortcut icon" href="favicon-8114d1fc.png">
<link rel="stylesheet" href="css/variables-8adf115d.css">
<link rel="stylesheet" href="css/general-2459343d.css">
<link rel="stylesheet" href="css/chrome-ae938929.css">
<link rel="stylesheet" href="css/print-9e4910d8.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="fonts/fonts-9644e21d.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" id="mdbook-highlight-css" href="highlight-493f70e1.css">
<link rel="stylesheet" id="mdbook-tomorrow-night-css" href="tomorrow-night-4c0ae647.css">
<link rel="stylesheet" id="mdbook-ayu-highlight-css" href="ayu-highlight-3fdfc3ac.css">
<!-- Custom theme stylesheets -->
<link rel="stylesheet" href="custom-03c054ce.css">
<!-- MathJax -->
<script async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<!-- Provide site root and default themes to javascript -->
<script>
const path_to_root = "";
const default_light_theme = "light";
const default_dark_theme = "navy";
window.path_to_searchindex_js = "searchindex-b348220b.js";
</script>
<!-- Start loading toc.js asap -->
<script src="toc-869b6773.js"></script>
</head>
<body>
<div id="mdbook-help-container">
<div id="mdbook-help-popup">
<h2 class="mdbook-help-title">Keyboard shortcuts</h2>
<div>
<p>Press <kbd>←</kbd> or <kbd>→</kbd> to navigate between chapters</p>
<p>Press <kbd>S</kbd> or <kbd>/</kbd> to search in the book</p>
<p>Press <kbd>?</kbd> to show this help</p>
<p>Press <kbd>Esc</kbd> to hide this help</p>
</div>
</div>
</div>
<div id="mdbook-body-container">
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script>
try {
let theme = localStorage.getItem('mdbook-theme');
let sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script>
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
let theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
const html = document.documentElement;
html.classList.remove('light')
html.classList.add(theme);
html.classList.add("js");
</script>
<input type="checkbox" id="mdbook-sidebar-toggle-anchor" class="hidden">
<!-- Hide / unhide sidebar before it is displayed -->
<script>
let sidebar = null;
const sidebar_toggle = document.getElementById("mdbook-sidebar-toggle-anchor");
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
} else {
sidebar = 'hidden';
sidebar_toggle.checked = false;
}
if (sidebar === 'visible') {
sidebar_toggle.checked = true;
} else {
html.classList.remove('sidebar-visible');
}
</script>
<nav id="mdbook-sidebar" class="sidebar" aria-label="Table of contents">
<!-- populated by js -->
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
<noscript>
<iframe class="sidebar-iframe-outer" src="toc.html"></iframe>
</noscript>
<div id="mdbook-sidebar-resize-handle" class="sidebar-resize-handle">
<div class="sidebar-resize-indicator"></div>
</div>
</nav>
<div id="mdbook-page-wrapper" class="page-wrapper">
<div class="page">
<div id="mdbook-menu-bar-hover-placeholder"></div>
<div id="mdbook-menu-bar" class="menu-bar sticky">
<div class="left-buttons">
<label id="mdbook-sidebar-toggle" class="icon-button" for="mdbook-sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="mdbook-sidebar">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M0 96C0 78.3 14.3 64 32 64H416c17.7 0 32 14.3 32 32s-14.3 32-32 32H32C14.3 128 0 113.7 0 96zM0 256c0-17.7 14.3-32 32-32H416c17.7 0 32 14.3 32 32s-14.3 32-32 32H32c-17.7 0-32-14.3-32-32zM448 416c0 17.7-14.3 32-32 32H32c-17.7 0-32-14.3-32-32s14.3-32 32-32H416c17.7 0 32 14.3 32 32z"/></svg></span>
</label>
<button id="mdbook-theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="mdbook-theme-list">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M371.3 367.1c27.3-3.9 51.9-19.4 67.2-42.9L600.2 74.1c12.6-19.5 9.4-45.3-7.6-61.2S549.7-4.4 531.1 9.6L294.4 187.2c-24 18-38.2 46.1-38.4 76.1L371.3 367.1zm-19.6 25.4l-116-104.4C175.9 290.3 128 339.6 128 400c0 3.9 .2 7.8 .6 11.6c1.8 17.5-10.2 36.4-27.8 36.4H96c-17.7 0-32 14.3-32 32s14.3 32 32 32H240c61.9 0 112-50.1 112-112c0-2.5-.1-5-.2-7.5z"/></svg></span>
</button>
<ul id="mdbook-theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="mdbook-theme-default_theme">Auto</button></li>
<li role="none"><button role="menuitem" class="theme" id="mdbook-theme-light">Light</button></li>
<li role="none"><button role="menuitem" class="theme" id="mdbook-theme-rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="mdbook-theme-coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="mdbook-theme-navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="mdbook-theme-ayu">Ayu</button></li>
</ul>
<button id="mdbook-search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="mdbook-searchbar">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M416 208c0 45.9-14.9 88.3-40 122.7L502.6 457.4c12.5 12.5 12.5 32.8 0 45.3s-32.8 12.5-45.3 0L330.7 376c-34.4 25.2-76.8 40-122.7 40C93.1 416 0 322.9 0 208S93.1 0 208 0S416 93.1 416 208zM208 352c79.5 0 144-64.5 144-144s-64.5-144-144-144S64 128.5 64 208s64.5 144 144 144z"/></svg></span>
</button>
</div>
<h1 class="menu-title">Modkit</h1>
<div class="right-buttons">
<a href="print.html" title="Print this book" aria-label="Print this book">
<span class=fa-svg id="print-button"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M128 0C92.7 0 64 28.7 64 64v96h64V64H354.7L384 93.3V160h64V93.3c0-17-6.7-33.3-18.7-45.3L400 18.7C388 6.7 371.7 0 354.7 0H128zM384 352v32 64H128V384 368 352H384zm64 32h32c17.7 0 32-14.3 32-32V256c0-35.3-28.7-64-64-64H64c-35.3 0-64 28.7-64 64v96c0 17.7 14.3 32 32 32H64v64c0 35.3 28.7 64 64 64H384c35.3 0 64-28.7 64-64V384zm-16-88c-13.3 0-24-10.7-24-24s10.7-24 24-24s24 10.7 24 24s-10.7 24-24 24z"/></svg></span>
</a>
</div>
</div>
<div id="mdbook-search-wrapper" class="hidden">
<form id="mdbook-searchbar-outer" class="searchbar-outer">
<div class="search-wrapper">
<input type="search" id="mdbook-searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="mdbook-searchresults-outer" aria-describedby="searchresults-header">
<div class="spinner-wrapper">
<span class=fa-svg id="fa-spin"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M304 48c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zm0 416c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zM48 304c26.5 0 48-21.5 48-48s-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48zm464-48c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zM142.9 437c18.7-18.7 18.7-49.1 0-67.9s-49.1-18.7-67.9 0s-18.7 49.1 0 67.9s49.1 18.7 67.9 0zm0-294.2c18.7-18.7 18.7-49.1 0-67.9S93.7 56.2 75 75s-18.7 49.1 0 67.9s49.1 18.7 67.9 0zM369.1 437c18.7 18.7 49.1 18.7 67.9 0s18.7-49.1 0-67.9s-49.1-18.7-67.9 0s-18.7 49.1 0 67.9z"/></svg></span>
</div>
</div>
</form>
<div id="mdbook-searchresults-outer" class="searchresults-outer hidden">
<div id="mdbook-searchresults-header" class="searchresults-header"></div>
<ul id="mdbook-searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script>
document.getElementById('mdbook-sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('mdbook-sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#mdbook-sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="mdbook-content" class="content">
<main>
<h1 id="find-highly-modified-motif-sequences"><a class="header" href="#find-highly-modified-motif-sequences">Find highly modified motif sequences</a></h1>
<p>The <code>modkit find-motifs</code> command will attempt to summarize short genome sequences (motifs) that are more found to be highly modified (i.e. enriched for methylation).
The input to this command is a bedMethyl generated by <code>modkit pileup</code> and the reference sequence used.
For example, to run the command with default settings (recommended):</p>
<pre><code class="language-bash">bedmethyl=/path/to/pileup.bed
ref=/path/to/reference.fasta
modkit motif search \
-i ${bedmethyl} \
-r ${ref} \
-o ./motifs.tsv \
--threads 32 \
--log ./modkit_find_motifs_log.txt
</code></pre>
<p>Specifying an output with <code>-o</code> will generate a machine-readable tab-separated-values file, a human-readable version of the table will always be logged to the terminal and the logfile.</p>
<p>If you have compressed your bedMethyl table with <code>bgzip</code> you can use the compressed table as well.
A compressed table with <code>tabix</code>-generated index is required to use the <code>--contig</code> option which will find motifs using only a single contig in the bedMethyl table.
This may be useful for applications such as metagenomics.</p>
<h2 id="output-format"><a class="header" href="#output-format">Output format</a></h2>
<p>All output tables are output in two formats, machine-readable and human-readable.
The human-readable tables are always output to the log and terminal, the machine-readable tables are output to files specified on the command line.</p>
<h3 id="machine-readable-table"><a class="header" href="#machine-readable-table">Machine-readable table</a></h3>
<div class="table-wrapper">
<table>
<thead>
<tr><th>column</th><th>name</th><th>description</th><th>type</th></tr>
</thead>
<tbody>
<tr><td>1</td><td>mod_code</td><td>code specifying the modification found in the motif</td><td>str</td></tr>
<tr><td>2</td><td>motif</td><td>sequence of identified motif using <a href="https://www.bioinformatics.org/sms/iupac.html">IUPAC</a> codes</td><td>str</td></tr>
<tr><td>3</td><td>offset</td><td>0-based offset into the motif sequence of the modified base</td><td>int</td></tr>
<tr><td>4</td><td>frac_mod</td><td>fraction of time this sequence is found in the <em>high modified</em> set col-5 / (col-5 + col-6)</td><td>float</td></tr>
<tr><td>5</td><td>high_count</td><td>number of occurances of this sequence in the <em>high-modified</em> set</td><td>int</td></tr>
<tr><td>6</td><td>low_count</td><td>number of occurances of this sequence in the <em>low-modified</em> set</td><td>int</td></tr>
<tr><td>7</td><td>mid_count</td><td>number of occurances of this sequence in the <em>mid-modified</em> set</td><td>int</td></tr>
</tbody>
</table>
</div>
<h3 id="human-readable-table"><a class="header" href="#human-readable-table">Human-readable table</a></h3>
<div class="table-wrapper">
<table>
<thead>
<tr><th>column</th><th>name</th><th>description</th><th>type</th></tr>
</thead>
<tbody>
<tr><td>1</td><td>motif</td><td>human-readable representation of the motif sequence with the modification code in brackets</td><td>str</td></tr>
<tr><td>2</td><td>frac_mod</td><td>fraction of time this sequence is found in the <em>high modified</em> set col-3 / (col-3 + col-4)</td><td>float</td></tr>
<tr><td>3</td><td>high_count</td><td>number of occurances of this sequence in the <em>high-modified</em> set</td><td>int</td></tr>
<tr><td>4</td><td>low_count</td><td>number of occurances of this sequence in the <em>low-modified</em> set</td><td>int</td></tr>
<tr><td>5</td><td>mid_count</td><td>number of occurances of this sequence in the <em>mid-modified</em> set</td><td>int</td></tr>
</tbody>
</table>
</div>
<h2 id="specifying-known-motifs"><a class="header" href="#specifying-known-motifs">Specifying known motifs</a></h2>
<p>Multiple motif sequences suspected to be present can be specified with the <code>--known-motif</code> option.
A machine-readable table of the motif sequences that are not found during the search can be specified with the <code>--known-motifs-table</code> option.
Using this option will add two columns to the above tables:</p>
<div class="table-wrapper">
<table>
<thead>
<tr><th>name</th><th>description</th><th>type</th></tr>
</thead>
<tbody>
<tr><td>status</td><td>equal, subset, superset, intersect, or disjoint describes the relationship of the discovered motif to the known motif, more details below</td><td>str</td></tr>
<tr><td>closest_known_motif</td><td>of all motifs specified with <code>--known-motif</code> the one that is most similar to the discovered motif</td><td>str</td></tr>
</tbody>
</table>
</div>
<p>The <code>status</code> column is the relationship of the set of sequences described by the motifs.
Say you have two motifs A and B they represent a set of sequences \(\mathbf{A}\) and \(\mathbf{B}\) .
For example, the motif <code>[a]</code> represents all sequences with at least one A primary base, whereas the set of sequences represented by G[a]TC is only {GATC}.
The status fills in the blank in the statement: \(\mathbf{A}\) \(?\) \(\mathbf{B}\).</p>
<p>If any of the known motifs are not found during the search process an additional table is also emitted in machine- and human-readable versions.</p>
<h3 id="machine-readable-table-1"><a class="header" href="#machine-readable-table-1">Machine-readable table</a></h3>
<div class="table-wrapper">
<table>
<thead>
<tr><th>column</th><th>name</th><th>description</th><th>type</th></tr>
</thead>
<tbody>
<tr><td>1</td><td>mod_code</td><td>code specifying the modification found in the motif</td><td>str</td></tr>
<tr><td>2</td><td>motif</td><td>sequence of identified motif using <a href="https://www.bioinformatics.org/sms/iupac.html">IUPAC</a> codes</td><td>str</td></tr>
<tr><td>3</td><td>offset</td><td>0-based offset into the motif sequence of the modified base</td><td>int</td></tr>
<tr><td>4</td><td>frac_mod</td><td>fraction of time this sequence is found in the <em>high modified</em> set col-5 / (col-5 + col-6)</td><td>float</td></tr>
<tr><td>5</td><td>high_count</td><td>number of occurances of this sequence in the <em>high-modified</em> set</td><td>int</td></tr>
<tr><td>6</td><td>low_count</td><td>number of occurances of this sequence in the <em>low-modified</em> set</td><td>int</td></tr>
<tr><td>7</td><td>mid_count</td><td>number of occurances of this sequence in the <em>mid-modified</em> set</td><td>int</td></tr>
<tr><td>8</td><td>status</td><td>equal, Subset, Superset, or Disjoint describes the relationship of the known motif to the closest discovered motif</td><td>str</td></tr>
<tr><td>9</td><td>closest_found_motif</td><td>which of the discovered motifs is most simuilar to the known motif</td><td>str</td></tr>
</tbody>
</table>
</div>
<h3 id="human-readable-table-1"><a class="header" href="#human-readable-table-1">Human-readable table</a></h3>
<div class="table-wrapper">
<table>
<thead>
<tr><th>column</th><th>name</th><th>description</th><th>type</th></tr>
</thead>
<tbody>
<tr><td>1</td><td>motif</td><td>human-readable representation of the motif sequence with the modification code in brackets</td><td>str</td></tr>
<tr><td>2</td><td>frac_mod</td><td>fraction of time this sequence is found in the <em>high modified</em> set col-3 / (col-3 + col-4)</td><td>float</td></tr>
<tr><td>3</td><td>high_count</td><td>number of occurances of this sequence in the <em>high-modified</em> set</td><td>int</td></tr>
<tr><td>4</td><td>low_count</td><td>number of occurances of this sequence in the <em>low-modified</em> set</td><td>int</td></tr>
<tr><td>5</td><td>mid_count</td><td>number of occurances of this sequence in the <em>mid-modified</em> set</td><td>int</td></tr>
<tr><td>6</td><td>status</td><td>equal, Subset, Superset, or Disjoint describes the relationship of the known motif to the closest discovered motif</td><td>str</td></tr>
<tr><td>7</td><td>closest_found_motif</td><td>which of the discovered motifs is most simuilar to the known motif</td><td>str</td></tr>
</tbody>
</table>
</div>
<h2 id="simple-description-of-the-search-algorithm"><a class="header" href="#simple-description-of-the-search-algorithm">Simple description of the search algorithm</a></h2>
<p>The first step in <code>find-motifs</code> is to categorize each genomic position in the pileup into one of three groups based on the <code>fraction modified</code> <a href="./intro_pileup.html#bedmethyl-column-descriptions">column in the bedMethyl</a>:</p>
<ul>
<li>Low-modified</li>
<li>Mid-modified</li>
<li>High-modified</li>
</ul>
<p>The threshold values for each group can be set on the command line (<code>--high-thresh</code> and <code>--low-thresh</code>).
For example, consider a high threshold of 0.6 and a low threshold of 0.2 the following 3 bedMethyl records would be put into the high-, low-, and mid-groups, respectively:</p>
<pre><code class="language-text">contig1 6 7 a 27 - 6 7 255,0,0 27 96.30 26 1 0 0 3 0 0
contig1 8 9 a 24 - 8 9 255,0,0 24 4.17 1 23 0 0 5 1 0
contig1 218 219 a 21 + 218 219 255,0,0 21 28.57 6 15 0 2 3 0 0
</code></pre>
<p>The sequence around each modified position is then collected from the reference FASTA file.
The length of the sequence can be set with the <code>--context-size</code> option, accepting two values: the number of bases upstream and the number of bases downstream of the modified location.
For example <code>--context-size 12 12</code> will collect 12 bases upstream and 12 bases downstream of the modified base for a maximum motif length of 25 base pairs.
The algorithm then iteratively expands, contracts, and merges sequences while the following criteria are met:</p>
<ul>
<li>The number of occurrences in the high-modified set is greater than <code>min_sites</code> (set by <code>--min-sites</code>).</li>
<li>The fraction \( \frac{\textit{H}}{\textit{H} + \textit{L}} \), is greater than <code>frac_mod</code> (set with <code>--min-frac-mod</code>), where \( \textit{H} \) and \( \textit{L} \) is the number of total sequence contexts in the high-modified and low-modified set, respectively.</li>
<li>The log-odds of the context being in the high-modified category is greater than <code>min_log_odds</code> (set with <code>--min-log-odds</code>).</li>
</ul>
<p>Once a motif sequence cannot be changed (made more general or more restrictive) without violating one of these criteria, the motif sequence is considered complete.
As the algorithm continues, context sequences that match discovered sequences are removed from consideration.</p>
<p>A secondary search step, called the “exhaustive search”, is also performed by starting with every k-mer (where k is less than the total sequence length, 3 by default, set with <code>--exhaustive-seed-len</code>) at every motif position.
The log-odds threshold for this search is usually higher and set with <code>--exhaustive-seed-min-log-odds</code>.
Decreasing this value can drastically increase computational time, see the next section for more details.</p>
<h2 id="options-to-decrease-or-limit-search-time"><a class="header" href="#options-to-decrease-or-limit-search-time">Options to decrease or limit search time.</a></h2>
<p>The optional (but recommended) exhaustive search step checks many sparsely defined sequences, called seeds, for enrichment as defined by <code>--exhaustive-seed-min-log-odds</code>.
The algorithm then refines the seeds above the threshold into candidate motifs using the method described <a href="intro_find_motifs.html#simple-description-of-the-search-algorithm">previously</a>.
An example seed is <code>GNNNNNNNNNNC[m]NNNNNNNNNNNA</code> using the modification code for 5mC.
The number of seeds is defined by the <code>--context-size</code> and <code>--exhaustive-seed-length</code> parameters.
For example, if <code>--context-size a b</code> is passed the seeds will be length \( a + b + 1 \).
The default value is <code>a = 12</code>, <code>b = 12</code> so the sequence length is 25, but we only use 24 of those positions, call this \( n \).
The default value for <code>--exhaustive-seed-length</code> is 3, call this \( k \).
Remember that there are 4 primary sequence bases.
So the number of seeds to search is \( k^4 * \binom{n}{k} \) or 129,536 seeds.
Most of these seeds will fall below the log-odds required, and not follow-on to refinement.
However, if a large number ( \( \gt 500 \) ) are above the log-odds threshold then this step can be very time consuming.
There are a couple options that can decrease or limit this run time, whist usually affording identical or very good results.</p>
<ol>
<li>A simple timeout.
When the search starts, the top-N (as ranked by log-odds) seeds are taken.
The search is run on this “batch”, if the timeout has not expired the next batch of N is taken.
If all of the seeds are not evaluated before running out of time, the results are returned but an ERROR message is displayed.</li>
</ol>
<pre><code class="language-bash"># specify that search should stop after 15 minutes
$ modkit motif search ... --search-timeout 15m
</code></pre>
<ol start="2">
<li>Top percent.
Only search the top P-% of seeds (or a maximum number).
So a command like this <code>--search-top-pct 20 --max-exhaustive-seeds 200</code> would search the top 20% of seeds as ranked by their log-odds for being motifs or the top 200 seeds if 20% of all of the seeds passing <code>--exhaustive-seed-min-log-odds</code> is greater than 200.
<strong>n.b.</strong> With default settings, in the most pathological settings 129,536 could be searched.</li>
</ol>
<pre><code class="language-bash"># only search the min(top 20% of seeds, 100 seeds)
$ modkit motif search ... --search-top-pct 20 --max-exhaustive-seeds 100
</code></pre>
<ol start="3">
<li>Batch and Narrow Optimization.
This algorithm is a combination of (1) and (2).
In this scenario, we take the top P-% of seeds (or the maximum allowed) as in (2).
But instead of stopping as in (2) we continue (as in (1)) but we remove contexts from consideration based on the motifs we’ve found before the next round.
At the end of the round, if zero motifs are found, we stop.</li>
</ol>
<pre><code class="language-bash"># same as (2), but continue to search after each batch
$ modkit motif search .. --search-top-pct 20 --max-exhaustive-seeds 100 --narrow-search
</code></pre>
<ol start="4">
<li>Batch and Narrow Optimization with Timeout.
This scenario is the same as (3), but if we’ve run out of time at the end of a round - stop.</li>
</ol>
<pre><code class="language-bash"># same as (3), but continue to search after each batch, until we've spent 15 minutes searching.
$ modkit motif search .. --search-top-pct 20 --max-exhaustive-seeds 100 --narrow-search --search-timeout 15m
</code></pre>
<h2 id="tuning-parameters-and---skip-search"><a class="header" href="#tuning-parameters-and---skip-search">Tuning parameters and <code>--skip-search</code></a></h2>
<p>The default parameters have been picked to be sufficiently sensitive, however if you decide to adjust the parameters in general increasing sensitivity will increase compute time.</p>
<ol>
<li>Increasing the <code>--min-frac-mod</code> will stop search earlier which will decrease compute time.</li>
<li>Decreasing <code>--min-sites</code> has the largest effect and can especially cause the secondary search to crawl more sequences.
Decreasing <code>--min-sites</code> along with <code>--skip-search</code> may be a useful technique to find very rare sequence motifs.</li>
<li>Increasing <code>--exhaustive-seed-min-log-odds</code> can drastically decrease compute time (sometimes while maintaining sensitivity).</li>
</ol>
<p>Also consider the additional steps in <a href="./perf_considerations.html#parallelism-in-find-motifs-when-to---skip-search">performance considerations.</a></p>
<h2 id="investigating-how-motifs-are-evaluated"><a class="header" href="#investigating-how-motifs-are-evaluated">Investigating how motifs are evaluated</a></h2>
<p>The <code>motif search</code> function uses JSON-lines structured logging that can be searched and queried for specific events.
The schema and some examples are described <a href="./motif_search_structured_logging.html">in another section</a>.</p>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="intro_motif_bed.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M41.4 233.4c-12.5 12.5-12.5 32.8 0 45.3l160 160c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L109.3 256 246.6 118.6c12.5-12.5 12.5-32.8 0-45.3s-32.8-12.5-45.3 0l-160 160z"/></svg></span>
</a>
<a rel="next prefetch" href="evaluate_motif.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M278.6 233.4c12.5 12.5 12.5 32.8 0 45.3l-160 160c-12.5 12.5-32.8 12.5-45.3 0s-12.5-32.8 0-45.3L210.7 256 73.4 118.6c-12.5-12.5-12.5-32.8 0-45.3s32.8-12.5 45.3 0l160 160z"/></svg></span>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="intro_motif_bed.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M41.4 233.4c-12.5 12.5-12.5 32.8 0 45.3l160 160c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L109.3 256 246.6 118.6c12.5-12.5 12.5-32.8 0-45.3s-32.8-12.5-45.3 0l-160 160z"/></svg></span>
</a>
<a rel="next prefetch" href="evaluate_motif.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M278.6 233.4c12.5 12.5 12.5 32.8 0 45.3l-160 160c-12.5 12.5-32.8 12.5-45.3 0s-12.5-32.8 0-45.3L210.7 256 73.4 118.6c-12.5-12.5-12.5-32.8 0-45.3s32.8-12.5 45.3 0l160 160z"/></svg></span>
</a>
</nav>
</div>
<template id=fa-eye><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M288 32c-80.8 0-145.5 36.8-192.6 80.6C48.6 156 17.3 208 2.5 243.7c-3.3 7.9-3.3 16.7 0 24.6C17.3 304 48.6 356 95.4 399.4C142.5 443.2 207.2 480 288 480s145.5-36.8 192.6-80.6c46.8-43.5 78.1-95.4 93-131.1c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C433.5 68.8 368.8 32 288 32zM432 256c0 79.5-64.5 144-144 144s-144-64.5-144-144s64.5-144 144-144s144 64.5 144 144zM288 192c0 35.3-28.7 64-64 64c-11.5 0-22.3-3-31.6-8.4c-.2 2.8-.4 5.5-.4 8.4c0 53 43 96 96 96s96-43 96-96s-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6z"/></svg></span></template>
<template id=fa-eye-slash><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 640 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M38.8 5.1C28.4-3.1 13.3-1.2 5.1 9.2S-1.2 34.7 9.2 42.9l592 464c10.4 8.2 25.5 6.3 33.7-4.1s6.3-25.5-4.1-33.7L525.6 386.7c39.6-40.6 66.4-86.1 79.9-118.4c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C465.5 68.8 400.8 32 320 32c-68.2 0-125 26.3-169.3 60.8L38.8 5.1zM223.1 149.5C248.6 126.2 282.7 112 320 112c79.5 0 144 64.5 144 144c0 24.9-6.3 48.3-17.4 68.7L408 294.5c5.2-11.8 8-24.8 8-38.5c0-53-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6c0 10.2-2.4 19.8-6.6 28.3l-90.3-70.8zm223.1 298L373 389.9c-16.4 6.5-34.3 10.1-53 10.1c-79.5 0-144-64.5-144-144c0-6.9 .5-13.6 1.4-20.2L83.1 161.5C60.3 191.2 44 220.8 34.5 243.7c-3.3 7.9-3.3 16.7 0 24.6c14.9 35.7 46.2 87.7 93 131.1C174.5 443.2 239.2 480 320 480c47.8 0 89.9-12.9 126.2-32.5z"/></svg></span></template>
<template id=fa-copy><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M502.6 70.63l-61.25-61.25C435.4 3.371 427.2 0 418.7 0H255.1c-35.35 0-64 28.66-64 64l.0195 256C192 355.4 220.7 384 256 384h192c35.2 0 64-28.8 64-64V93.25C512 84.77 508.6 76.63 502.6 70.63zM464 320c0 8.836-7.164 16-16 16H255.1c-8.838 0-16-7.164-16-16L239.1 64.13c0-8.836 7.164-16 16-16h128L384 96c0 17.67 14.33 32 32 32h47.1V320zM272 448c0 8.836-7.164 16-16 16H63.1c-8.838 0-16-7.164-16-16L47.98 192.1c0-8.836 7.164-16 16-16H160V128H63.99c-35.35 0-64 28.65-64 64l.0098 256C.002 483.3 28.66 512 64 512h192c35.2 0 64-28.8 64-64v-32h-47.1L272 448z"/></svg></span></template>
<template id=fa-play><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 384 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M73 39c-14.8-9.1-33.4-9.4-48.5-.9S0 62.6 0 80V432c0 17.4 9.4 33.4 24.5 41.9s33.7 8.1 48.5-.9L361 297c14.3-8.7 23-24.2 23-41s-8.7-32.2-23-41L73 39z"/></svg></span></template>
<template id=fa-clock-rotate-left><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M75 75L41 41C25.9 25.9 0 36.6 0 57.9V168c0 13.3 10.7 24 24 24H134.1c21.4 0 32.1-25.9 17-41l-30.8-30.8C155 85.5 203 64 256 64c106 0 192 86 192 192s-86 192-192 192c-40.8 0-78.6-12.7-109.7-34.4c-14.5-10.1-34.4-6.6-44.6 7.9s-6.6 34.4 7.9 44.6C151.2 495 201.7 512 256 512c141.4 0 256-114.6 256-256S397.4 0 256 0C185.3 0 121.3 28.7 75 75zm181 53c-13.3 0-24 10.7-24 24V256c0 6.4 2.5 12.5 7 17l72 72c9.4 9.4 24.6 9.4 33.9 0s9.4-24.6 0-33.9l-65-65V152c0-13.3-10.7-24-24-24z"/></svg></span></template>
<!-- Livereload script (if served using the cli tool) -->
<script>
const wsProtocol = location.protocol === 'https:' ? 'wss:' : 'ws:';
const wsAddress = wsProtocol + "//" + location.host + "/" + "__livereload";
const socket = new WebSocket(wsAddress);
socket.onmessage = function (event) {
if (event.data === "reload") {
socket.close();
location.reload();
}
};
window.onbeforeunload = function() {
socket.close();
}
</script>
<script>
window.playground_copyable = true;
</script>
<script src="elasticlunr-ef4e11c1.min.js"></script>
<script src="mark-09e88c2c.min.js"></script>
<script src="searcher-c2a407aa.js"></script>
<script src="clipboard-1626706a.min.js"></script>
<script src="highlight-abc7f01d.js"></script>
<script src="book-a0b12cfe.js"></script>
<!-- Custom JS scripts -->
</div>
</body>
</html>