無根樹演算法

❶ 基因家族擴張與收縮分析及物種進化樹構建（上）

首先，選取不同物種的Protein數據集：Arabidopsis_thaliana.fa；Citrus_grandis.fa；Dimocarpus_longan.fa；Durio_zibethinus.fa；Prunus_persica.fa； Vitis_vinifera.fa；Citrus_clementina.fa；Citrus_sinensis.fa；Diospyros_oleifera.fa；Malus_domestica.fa；Oryza_sativa.fa；Pyrus_communis.fa
然後進行數據處理，去冗餘，只保留最長轉錄本，去除可變剪切：
python3 removeRendantProteins.py -i input.fa -o output.fa
removeRendantProteins.py

將處理好的數據置於一個文件夾中「Dataset」

OrthoFinder這個軟體，之前有一篇文章已經介紹過了，這里就不在贅述，這個軟體安裝十分友好，棗悄春直接conda安裝即可；
nohup orthofinder -f Dataset -M msa -S diamond -T iqtree -t 24 -a 24 2> orthofinder.log &
orthofinder參數詳情：
-t 並行序列搜索線程數（默認= 16）
-a 並行分析線程數（默認值運友= 1）
-M 基因樹推斷方法。可選：dendroblast和msa（默認= dendroblast）
-S 序列搜索程序（默認= blast）選項：blast，mmseqs,，blast_gz，diamond（推薦使用diamond，比對速度很給力）
-A 多序列聯配方式，需要添加參數-M msa時才有效；（默認= mafft）可選擇：muscle，mafft
-T 建樹方法，需要添加參數-M msa時才有效，（默認 = fasttree）可選：iqtree，raxml-ng，fasttree，raxml
-s <文件> 可指定特定的根物種樹
-I 設定MCL的通脹參數（默認 = 1.5）
-x Info用於以othoXML格式輸出結果
-p <dir>將臨時pickle文件寫入到<dir>
-l 只執行單向序列搜索
-n 名稱以附加到結果目凳耐錄
-h 列印幫助文本
如果只需要查找直系同源基因，只需接「-f」 參數即可；此步也可建樹，採用默認的建樹方法fasttree，為無根樹。
nohup orthofinder -f Dataset &
如果添加-M msa -T iqtree設定製定參數，可按照設定的參數使用最大似然法構建有根的物種進化樹，構建的樹為STAG樹。
nohup orthofinder -f Dataset -M msa -S diamond -T iqtree -t 24 -a 24 2> orthofinder.log &

關於構建系統進化樹，有很多種做法，常見的有利用物種全部的蛋白序列，構建STAG物種樹；也有使用單拷貝直系同源基因構建的物種進化樹，關於這一點，OrthoFinder查找同源基因，可以輸出直系單拷貝同源基因的序列結果，後續也可使用其他構樹軟體及演算法進行進化樹構建。關於建樹方法，則有距離矩陣法、最大簡約法、最大似然法以及貝葉斯；當然目前主流採用的基本為最大似然法和貝葉斯，其中貝葉斯演算法計算量巨大，耗時最久，其構建的樹也認為最為「逼真」，但文章中使用較多的還是最大似然法，其耗時也需蠻久。

OrthoFinder輸出的結果會在OrthoFinder文件夾下面的以日期命名的文件夾中，如：~/OrthoFinder/Results_May08

其中，我們可以用Orthogroups.GeneCount.tsv來作為CAFE的輸入文件，分析基因家族的擴張與收縮；使用SpeciesTree_rooted.txt作為推斷的物種樹，並使用r8s，從中提取超度量樹（ultrametric tree）即時間樹；

python cafetutorial_prep_r8s.py -i SpeciesTree_rooted.txt -o r8s_ctl_file.txt -s 6650255 -p 'Oryza_sativa,Arabidopsis_thaliana' -c '152'
參數：
-i path_tree_file: path to .txt file containing tree in NEWICK format
-s n_sites: number of sites in alignment that was used to infer species tree
-p list_of_spp_tuples: list of tuples (each tuple being two species IDs whose mrca's age we are constraining; e.g., [('ENSG00','ENSPTR'),('ENSFCA','ENSECA')]
-c list_of_spp_cal_points: list of flats, one for each tuple in list_of_spp_tuples (e.g., [6.4,80])
-s 即用於推斷物種樹的比對序列鹼基數目；
-p 已知物種樹中的一對物種；
-c 已知一對物種的分化年限：
可在 timetree 網站查詢：為152 mya

conda install cafe

cafetutorial_clade_and_size_filter.py

vim cafetutorial_run.sh

tree即為r8s提取的超度量樹；

python cafetutorial_report_analysis.py -i reports/report_run.cafe -o reports/summary_run
summary_run_node.txt：統計每個節點中擴張，收縮的基因家族數目；
summary_run_fams.txt：具體發生變化的基因家族

python3 /home/Tools/CAFE_fig/CAFE_fig.py resultfile.cafe -pb 0.05 -pf 0.05 --mp test/ -g svg --count_all_expansions
輸出svg格式的文件，可導入AI編輯美化；

CAFE_fig運行報錯：（mole 'ete3' has no attribute 'TreeStyle'）
報錯解決：
vim /home/Tools/CAFE_fig/CAFE_fig.py

程序還在運行，後續貼出結果圖。

OrthoFinder
timetree
http://www.chenlianfu.com/?tag=genomecomparison
https://www.jianshu.com/p/146093c91e2b
r8s
【OrthoFinder】
Emms, D.M., Kelly, S. OrthoFinder: solving fundamental biases in whole genome comparisons dramatically improves orthogroup inference accuracy. Genome Biol 16, 157 (2015) ( https://doi.org/10.1186/s13059-015-0721-2 )
Emms, D.M., Kelly, S. OrthoFinder: phylogenetic orthology inference for comparative genomics. Genome Biol 20, 238 (2019) https://doi.org/10.1186/s13059-019-1832-y )
【CAFE v.4.2.1】
Han, M. V., Thomas, G. W. C., Lugo-Martinez, J., and Hahn, M. W. Estimating gene gain and loss rates in the presence of error in genome assembly and annotation using CAFE 3. Molecular Biology and Evolution 30, 8 (2013)
【iqtree v. 1.6.12】
Lam-Tung Nguyen, Heiko A. Schmidt, Arndt von Haeseler, and Bui Quang Minh (2015) IQ-TREE: A fast and effective stochastic algorithm for estimating maximum likelihood phylogenies. Mol Biol Evol, 32:268-274. https://doi.org/10.1093/molbev/msu300
【modelFinder】
Subha Kalyaanamoorthy, Bui Quang Minh, Thomas KF Wong, Arndt von Haeseler, and Lars S Jermiin (2017) ModelFinder: Fast model selection for accurate phylogenetic estimates. Nature Methods, 14:587–589. https://doi.org/10.1038/nmeth.4285
【R8s v. 1.81】
Sanderson M J. R8s: inferring absolute rates of molecular evolution and divergence times in the absence of a molecular clock. Bioinformatics, 2003, 19(2): 301-302.
【STAG tree】
Emms D.M. & Kelly S. STAG: Species Tree Inference from All Genes (2018), bioRxiv https://doi.org/10.1101/267914

直系同源低拷貝核基因（orthologous low- nuclear genes, LCN）：在進化過程中，新基因通常來自事先存在的基因，新基因的功能從先前基因的功能進化而來。新基因的原材料來自基因組區域的重復，這種重復可包括一個或多個基因。作為物種形成的伴隨事件而被重復，並繼續保持相同功能的基因，稱為直系同源基因（orthologous）。新的基因功能可由在單個物種的基因組中發生的重復引起的。在一個基因組內部的重復導致旁系同源基因（paralogous gene）。
最大似然法（maximum likelihood method）：使用概率模型，尋找能夠以較高概率產生觀察數據的系統發生樹。
外群的選擇：大多數的種系發生重建方法會產生無根樹，但是觀察樹的拓撲結構無法識別樹根應在哪一分支上。實際上，對於要證實哪一個分類單元的分支先於其他的分類單元，樹根必須確定。在無根樹中設定一個根，最簡單的方法是在數據集中增加一個外群（outgroup）。外群是一種分類操作單元，且有外部信息表明外群在所有分類群之前就已分化。研究演化歷史，一般選擇比目標序列具有較早進化歷史的序列作為外類群。
Bootstrap support: bootstrap是統計學上一種非參數統計方法，通過有放回的隨機抽樣，構建分類回歸樹。Jackknife與bootstrap類似，只是每次抽樣時會去除幾個樣本，像小刀一樣切去一部分。所謂bootstrap法就是從整個序列的鹼基（氨基酸）中任意選取一半，剩下的一半序列隨機補齊組成一個新的序列。這樣，一個序列就可以變成許多序列，一個序列組也就可以變成許多個序列組。根據某種演算法（距離矩陣法、最大簡約法、最大似然法），每個多序列組都可以生成一個進化樹。將生成的許多進化樹進行比較，按照多數規則（majority-rule）就會得到一個最「逼真」的進化樹。

❷ 數據結構中的是樹形的結構有哪些，演算法叫什麼名字

基礎類：二叉搜索（排序）樹，線索二叉樹，哈夫曼樹（最優二叉樹），二叉堆
平衡樹類：AVL，紅黑樹，2-3樹，2-3-4樹，B樹，B+樹，B-樹，treap，SBT。
優先隊列類：左高樹（左偏樹，可並堆，斜堆），雙端堆，斐波那契堆
集合類：並查集
區間樹類：線段樹，劃分樹，歸並樹，樹狀數組
字母樹類：字典樹，後綴樹。AC自動機演算法
動態樹類：伸展樹
計算幾何類：KD-tree （塊狀樹），4叉樹
RMQ轉LCA：笛卡爾樹
圖論相關：最小生成樹，無根樹
其它：敗者樹，博弈樹