broccoli_rs/lib.rs
1//! <p align="center">
2//! <img width="300" src="https://raw.githubusercontent.com/rderelle/Broccoli/master/images/logo_broccoli.png" alt="Broccoli">
3//! </p>
4//!
5//! Broccoli is designed to infer orthologous groups and orthologous pairs using a mixed phylogeny-network approach. It also detects
6//! chimeric proteins resulting from gene-fusion events and assigns these proteins to the corresponding orthologous groups.
7//!
8//! This page is the user manual of the `broccoli` command-line program.
9//!
10//! <p align="center">
11//! <img width="650" src="https://raw.githubusercontent.com/rderelle/Broccoli/master/images/overview_broccoli.png" alt="Overview of the 4 steps of Broccoli">
12//! </p>
13//!
14//! # Installation
15//!
16//! The easiest way to install Broccoli is via [Bioconda](https://bioconda.github.io/),
17//! which also installs DIAMOND and FastTree:
18//!
19//! ```bash
20//! conda install bioconda::broccoli
21//! ```
22//!
23//! Alternatively, with a [Rust toolchain](https://www.rust-lang.org/tools/install)
24//! installed, it can be built from the GitHub repository:
25//!
26//! ```bash
27//! git clone https://github.com/rderelle/Broccoli.git
28//! cd Broccoli
29//! cargo build --release # executable: target/release/broccoli
30//! ```
31//!
32//! Broccoli uses two external programs during step 2 (both are installed by Bioconda):
33//!
34//! - [DIAMOND](https://github.com/bbuchfink/diamond) v0.9.30 or above (similarity
35//! searches). The `-combined_search` option needs a DIAMOND release that supports
36//! `--taxon-k`.
37//! - [FastTree](http://www.microbesonline.org/fasttree/) v2.1.11 or above, in its
38//! single-threaded version (phylogenetic analyses; Broccoli runs many FastTree
39//! instances in parallel). FastTree is not needed with `-phylogenies nj`.
40//!
41//! By default they should be named `diamond` and `fasttree` and be in your `PATH`;
42//! otherwise, give their location with `-path_diamond` and `-path_fasttree`.
43//!
44//! # Quick start
45//!
46//! The only mandatory argument is the directory containing the proteome files:
47//!
48//! ```bash
49//! # display the help menu
50//! broccoli -help
51//!
52//! # run the whole pipeline on 8 threads
53//! broccoli -dir proteomes -threads 8
54//!
55//! # fastest settings: one combined DIAMOND search and built-in NJ trees
56//! broccoli -dir proteomes -threads 8 -combined_search -phylogenies nj
57//!
58//! # orthologous groups only (steps 1 to 3), with maximum-likelihood trees
59//! broccoli -dir proteomes -threads 8 -steps 1,2,3 -phylogenies ml
60//!
61//! # write the dir_step* directories in output_broccoli/ instead of the current directory
62//! broccoli -dir proteomes -threads 8 -output output_broccoli
63//! ```
64//!
65//! Broccoli writes its temporary and output files in 4 directories, `dir_step1` to
66//! `dir_step4` (one per step), created in the **current directory**, or in the
67//! directory given with `-output` (e.g. `-output output_broccoli`). The main
68//! results are:
69//!
70//! - `dir_step3/orthologous_groups.txt`
71//! - `dir_step3/chimeric_proteins.txt`
72//! - `dir_step4/orthologous_pairs.txt`
73//!
74//! # Input data
75//!
76//! The input is a directory containing one proteome file per species:
77//!
78//! - sequences in FASTA format;
79//! - file extension `.fas`, `.fasta` or `.faa` (any case), optionally gzipped
80//! (e.g. `human.faa.gz`); other files in the directory are ignored;
81//! - the protein name is the part of the FASTA header before the first space.
82//! Protein names should be unique across all files: if not, Broccoli prints a
83//! warning and lists the duplicates in `dir_step1/duplicate_names.txt`.
84//!
85//! Species are identified by their file names in all output tables, so naming the
86//! files after the species (e.g. `Homo_sapiens.fasta`) makes the results easier to read.
87//!
88//! # How Broccoli works
89//!
90//! The analysis is divided into 4 steps, each writing its files in its own directory:
91//!
92//! 1. **k-mer simplification** (`dir_step1`): within each proteome, proteins sharing a
93//! k-mer (i.e. an identical fragment) are grouped and only the longest protein of
94//! each group is kept for the next steps. This removes redundancy (isoforms,
95//! identical copies) and speeds up the analysis. The removed proteins are added
96//! back, alongside their representative, in the final outputs.
97//! 2. **phylomes** (`dir_step2`): all-against-all similarity searches with DIAMOND
98//! (keeping the best hits in each species), then, for each protein whose hits
99//! contain several proteins of the same species, a phylogenetic tree is built from
100//! the trimmed alignment of its hits.
101//! 3. **network analysis** (`dir_step3`): orthologous relationships are extracted from
102//! the trees and combined into an orthology network, in which orthologous groups
103//! are identified by label propagation. Chimeric proteins are then detected and
104//! assigned to all their orthologous groups, and spurious hits are removed.
105//! 4. **orthologous pairs** (`dir_step4`): within each orthologous group, pairs of
106//! proteins are classified as orthologs or paralogs from their relationships in
107//! all the trees they appear in.
108//!
109//! Two things to keep in mind:
110//!
111//! - each step requires the directories generated by the previous steps, so steps
112//! can be run separately (e.g. `-steps 1,2,3` then later `-steps 4`), but always
113//! from the same directory, or with the same `-output`;
114//! - each step first deletes its own directory if it exists, to avoid mixing files
115//! from different runs. Rename or move the results you want to keep before
116//! re-running a step, or use a different `-output` for each analysis.
117//!
118//! # Output files
119//!
120//! Orthologous groups are named `OG_1`, `OG_2`, ... and contain proteins from at
121//! least 2 species. Every step also writes a log file (`log_step1.txt` to
122//! `log_step3.txt`) in its directory.
123//!
124//! ## Orthologous groups and chimeric proteins (`dir_step3`)
125//!
126//! | File | Content |
127//! |------|---------|
128//! | `orthologous_groups.txt` | one orthologous group per line: its name, then the names of its proteins separated by spaces |
129//! | `table_OGs_protein_counts.txt` | number of proteins of each species (columns) in each orthologous group (rows) |
130//! | `table_OGs_protein_names.txt` | same table with the protein names instead of their number |
131//! | `chimeric_proteins.txt` | chimeric proteins: species file, protein name, number and list of the orthologous groups it belongs to |
132//! | `unclassified_proteins.txt` | proteins not assigned to any orthologous group |
133//! | `statistics_per_OG.txt` | for each orthologous group: number of species, number of proteins after the k-mer simplification and in total, clustering coefficient |
134//! | `statistics_per_species.txt` | percentage and number of proteins of each species assigned to an orthologous group |
135//! | `statistics_nb_OGs_VS_nb_species.txt` | number of orthologous groups containing 2, 3, ... species |
136//! | `log_step3.txt` | size of the orthology network, distribution of the edge weights, numbers of communities and chimeric proteins |
137//!
138//! `OGs_in_network.txt` is an intermediate file used by step 4.
139//!
140//! ## Orthologous pairs (`dir_step4`)
141//!
142//! `orthologous_pairs.txt` lists one pair of orthologous proteins per line (two
143//! protein names separated by a tab).
144//!
145//! ## Other files
146//!
147//! - `dir_step1/log_step1.txt`: number of proteins in each proteome before and after
148//! the k-mer simplification.
149//! - `dir_step2/log_step2.txt`: for each species, number of proteins with a
150//! phylogeny, without a phylogeny (no duplicated species among their hits), with an
151//! empty alignment after trimming, and with a failed tree.
152//! - the other files in `dir_step1` and `dir_step2` (reduced proteomes, similarity
153//! hits, trees) are intermediate files used by the next steps.
154//!
155//! # Options
156//!
157//! Options are given with a single dash (e.g. `-threads 8`); `-help` (or `-h`)
158//! prints the list of options with their default values.
159//!
160//! ## General options
161//!
162//! | Option | Default | Description |
163//! |--------|---------|-------------|
164//! | `-steps` | `1,2,3,4` | steps to perform, comma separated, consecutive |
165//! | `-threads` | `1` | number of threads |
166//! | `-output`, `-o` | current directory | directory where the `dir_step*` directories are written (created if needed) |
167//!
168//! `-steps` selects which steps are performed. For instance, if you only need
169//! orthologous groups, use `-steps 1,2,3`. The steps must be consecutive
170//! (`-steps 1,3` is not valid).
171//!
172//! ## Step 1: k-mer simplification
173//!
174//! | Option | Default | Description |
175//! |--------|---------|-------------|
176//! | `-dir` | *required* | directory containing the proteome files (full or relative path) |
177//! | `-kmer_size` | `100` | length of the k-mers |
178//! | `-kmer_min_aa` | `15` | minimum number of different amino acids a k-mer should contain |
179//!
180//! Proteins of the same proteome sharing at least one k-mer of length `-kmer_size` are
181//! grouped, and only the longest one is kept. K-mers made of fewer than `-kmer_min_aa`
182//! different amino acids, or containing `X` or `*`, are ignored to avoid grouping
183//! proteins through low-complexity or repetitive regions.
184//!
185//! ## Step 2: phylomes
186//!
187//! | Option | Default | Description |
188//! |--------|---------|-------------|
189//! | `-path_diamond` | `diamond` | path of the DIAMOND executable |
190//! | `-path_fasttree` | `fasttree` | path of the FastTree executable |
191//! | `-e_value` | `0.001` | e-value threshold of the similarity searches |
192//! | `-nb_hits` | `6` | maximum number of hits per species |
193//! | `-max_gap` | `0.7` | maximum fraction of gaps per alignment position |
194//! | `-phylogenies` | `bionj` | tree-building method: `bionj`, `me`, `ml` or `nj` |
195//! | `-combined_search` | off | one DIAMOND search against a combined database |
196//!
197//! `-e_value` and `-nb_hits` correspond to the DIAMOND options `--evalue` and
198//! `--max-target-seqs` (applied per species). `-max_gap` controls the trimming of the
199//! alignments: positions with a fraction of gaps equal to or above this value are removed.
200//!
201//! `-phylogenies` sets how gene trees are built:
202//!
203//! - `bionj`: FastTree BioNJ (fast);
204//! - `me`: FastTree minimum evolution (slower, more precise);
205//! - `ml`: FastTree maximum likelihood (much slower, most precise);
206//! - `nj`: built-in neighbor-joining, much faster per tree than FastTree and does not
207//! require FastTree; results are only marginally less accurate than with `bionj`.
208//!
209//! By default, Broccoli runs one DIAMOND search per pair of proteomes. With
210//! `-combined_search`, it runs a single search of all proteins against one database
211//! containing all proteomes, which avoids repeating the database and query setup and
212//! makes step 2 much faster, with near-identical hits. Two caveats: it uses more
213//! memory, and since e-values are computed with the mean proteome size, it should not
214//! be used with proteomes of very different sizes.
215//!
216//! ## Step 3: network analysis
217//!
218//! | Option | Default | Description |
219//! |--------|---------|-------------|
220//! | `-sp_overlap` | `0.5` | maximum ratio of overlapping species in phylogenetic trees |
221//! | `-min_weight` | `0.1` | minimum weight for an edge to be kept in the orthology network |
222//! | `-min_nb_hits` | `2` | spurious hits: minimum number of hits within the orthologous group |
223//! | `-chimeric_shared` | `0.5` | chimeric proteins: minimum fraction of connected proteins in each orthologous group |
224//! | `-chimeric_nb_sp` | `3` | chimeric proteins: minimum number of species connected in each orthologous group |
225//!
226//! `-sp_overlap` controls how orthologous groups are delineated in the trees. At each
227//! node, the ratio is the maximum fraction of species shared between the leaves
228//! already browsed and the sister leaves. Low values (e.g. 0.3) produce small, tightly
229//! defined orthologous groups, while high values (e.g. 0.7) produce larger groups,
230//! similar to the orthogroups of OrthoFinder.
231//!
232//! `-min_weight` cleans the orthology network by removing weak edges (the weight of an
233//! edge is relative to the strongest edge of each protein). Besides removing spurious
234//! connections, this speeds up step 3.
235//!
236//! The 3 remaining options control the two corrections applied after the
237//! identification of orthologous groups:
238//!
239//! - **spurious hits**: a protein is removed from its orthologous group if it has
240//! fewer than `-min_nb_hits` DIAMOND hits with other proteins of the group (only
241//! applied to groups containing more than `-min_nb_hits` + 1 proteins);
242//! - **chimeric proteins**: a protein connected to several orthologous groups through
243//! non-overlapping regions of its sequence is considered chimeric (gene fusion) if,
244//! for each group, it is connected to at least a fraction `-chimeric_shared` of the
245//! group's proteins, belonging to at least `-chimeric_nb_sp` species. It is then
246//! assigned to all these groups.
247//!
248//! ## Step 4: orthologous pairs
249//!
250//! | Option | Default | Description |
251//! |--------|---------|-------------|
252//! | `-ratio_ortho` | `0.5` | minimum ratio ortho / (ortho + para) to report a pair |
253//! | `-not_same_sp` | off | ignore orthologous relationships between proteins of the same species |
254//!
255//! For each pair of proteins of an orthologous group, Broccoli counts how many times
256//! they appear as orthologs or as paralogs across the trees. `-ratio_ortho` sets the
257//! precision/recall trade-off: increasing it improves the precision of the
258//! orthologous pairs, decreasing it improves their recall.
259//!
260//! `-not_same_sp` discards pairs of proteins from the same species (e.g. for the
261//! Quest for Orthologs benchmark).
262//!
263//! # Tips and FAQ
264//!
265//! ### How to make Broccoli faster?
266//!
267//! The most time-consuming parts of the analysis are the similarity searches and
268//! the phylogenetic analyses (step 2):
269//!
270//! - `-combined_search` speeds up the similarity searches (see the caveats in
271//! [step 2](#step-2-phylomes));
272//! - `-phylogenies nj` speeds up the phylogenetic analyses;
273//! - reducing `-nb_hits` reduces the number of sequences in alignments and trees, at
274//! a potential cost in precision;
275//! - reducing `-kmer_size` simplifies the proteomes further at step 1, at the risk of
276//! grouping paralogs together. This has nearly no effect on prokaryotic
277//! proteomes, and in some species many unrelated proteins share identical fragments
278//! (e.g. viral domains in *Trichomonas vaginalis*).
279//!
280//! As an example, with 60 fungal proteomes on 8 threads (steps 1 to 3; Intel Xeon
281//! Platinum 8358 @ 2.60 GHz):
282//!
283//! | Options | Runtime (min) | Peak memory (GB) |
284//! |---------|---------------|------------------|
285//! | default | 419 | 4 |
286//! | `-combined_search` | 196 | 18 |
287//! | `-combined_search -phylogenies nj` | 106 | 18 |
288//!
289//! ### How to make Broccoli more precise?
290//!
291//! Minimum-evolution or maximum-likelihood trees (`-phylogenies me` or
292//! `-phylogenies ml`) improve the delineation of closely related orthologous groups,
293//! but increase the runtime of the phylogenetic analyses by a factor of about 30 and
294//! 100 respectively.
295//!
296//! Lowering `-sp_overlap` (e.g. 0.4) improves precision but lowers recall (small
297//! orthologous groups missing some divergent in-paralogs), which can be suitable for
298//! the identification of phylogenomic markers.
299//!