1  ---
 2  title: Algorithms
 3  ---
 4  
 5  <!-- MarkdownTOC -->
 6  
 7  - [Single probe design](#single-probe-design)
 8      - [Features](#features)
 9      - [Algorithm](#algorithm)
10  - [Spotting probe design](#spotting-probe-design)
11      - [Features](#features-1)
12      - [Algorithm](#algorithm-1)
13  
14  <!-- /MarkdownTOC -->
15  
16  We included two algorithms in `ifpd`: the first to design a single probe in a genomic region of interest (gROI), and the second to design a number of homogeneously spread probes in a gROI (i.e, to design a *spotting* probe).
17  
18  Both algorithms are based on the calculation of either single or spotting probe-related features. We will go more into the details of both features and algorithms in the following sections.
19  
20  ##  Single probe design
21  
22  This algorithm is implemented in the [`ifpd_query_probe` script]({{ site.baseurl}}/scripts#ifpd_query_probe).
23  
24  ### Features
25  
26  * `size`: defined as the distance between the genomic coordinates of the first base covered by the first oligo, and the last base covered by the last oligo.
27  * `centrality`: ratio between the distance between the gROI midpoint and the probe midpoint, and the gROI's half-size. It spans from 0, when the probe midpoint sits on the gROI's border, to 1, when the probe midpoint coincides to the gROI's midpoint.
28  * `homogeneity` of inter-oligo distance: defined as the reciprocal of the inter-oligo distance standard deviation. The distance between two consecutive oligos is defined as the difference in genomic coordinates of the last base covered by the first oligo, and the first base covered by the second oligo.
29  
30  ### Algorithm
31  
32  The single probe design algorithms requires the following inputs:
33  
34  * A database of FISH oligonucleotides.
35  * The genomic region of interest, *e.g.*, `chr1:1000000-1001000`.
36  * The number of oligos for the probe (*N<sub>O</sub>*).
37  * The priority order for the aforementioned features. Default is: (1) `size`, (2) `homogeneity`, and (3) `centrality`.
38  * A range (fraction, *F*) for the filter step, which is 0.1 by default.
39  
40  The algorithm performs the following steps:
41  
42  1. Retrieve all oligonucleotides in the region of interest, from the database.
43  2. Identify all sets of *N<sub>O</sub>* consecutive oligonucleotides from the retrieved ones.
44  3. Calculate the three features for each oligonucleotide set.
45  4. Discard all sets that have a priority 1 feature (`size` by default) outside a range around the *best value*. This step behaves differently depending on the feature, using the following ranges:
46      * `size`: `min(size)±F*min(size)`
47      * `homogeneity`: `max(homogeneity)±F*max(homogeneity)`
48      * `centrality`: `max(centrality)±F*max(centrality)`
49  5. Sort the remaining sets based on the priority 2 feature (`homogeneity` by default), from the *best* to the *worst* value. This step behaves differently depending on the feature, sorting as follows:
50      * `size`: from `min(size)` to `max(size)`
51      * `homogeneity`: from `max(homogeneity)` to `min(homogeneity)`
52      * `centrality`: from `max(centrality)` to `min(centrality)`
53  6. Provide as output the first set in the sorted list, which is considered to be the *optimal* probe.
54  
55  ##  Spotting probe design
56  
57  This algorithm is implemented in the [`ifpd_query_set` script]({{ site.baseurl}}/scripts#ifpd_query_set).
58  
59  ### Features
60  
61  * `homogeneity` of inter-probe distance and probe size: defined as the average between the reciprocal of the standard deviation of inter-probe distance and probe size, respectively. The distance between two consecutive probes is the difference in genomic coordinates between the last base covered by the last oligo in the first probe, and the first base covered by the first oligo in the second probe.
62  
63  ### Algorithm
64  
65  The spotting probe design algorithms requires the following inputs:
66  
67  * A database of FISH oligonucleotides.
68  * The genomic region of interest, *e.g.*, `chr1:1000000-1001000`.
69  * The number of probes to be designed (*N<sub>P</sub>*)
70  * The number of oligos for a probe (*N<sub>O</sub>*).
71  * The priority order for the aforementioned features. Default is: (1) `size`, (2) `homogeneity`, and (3) `centrality`.
72  * A range (fraction, *F*) for the filter step, which is 0.1 by default.
73  * A fraction (*W*) for the window shift.
74  
75  The algorithm works as following:
76  
77  1. Retrieve all oligonucleotides in the region of interest, from the database.
78  2. Identify all sets of *N<sub>O</sub>* consecutive oligonucleotides from the retrieved ones.
79  3. Calculate the three features for each oligonucleotide set.
80  4. Divide the region into *N<sub>P</sub>*+1 windows.
81  5. For each of the first *N<sub>P</sub>* windows, run the <u>single</u> probe design algorithm and identify the *optimal* probe.
82  6. Define the set of *N<sub>P</sub>* *optimal* probes as a *spotting* probe.
83  7. Shift the windows of *W* and repeat steps 4-6 until the whole region has been covered. (*e.g.*, if *W* is 0.1, after 11 iterations).
84  8. For each *spotting* probe, calculate the `homogeneity` of inter-probe distance and probe size, and use it to sort in decreasing order alongside the number of probes (some sets might have less probes due to lack of oligonucleotides in a window).
85  9. Provide as output the first *spotting* probe in the sorted list, which is considered to be the *optimal spotting* probe.