1.介绍
ANGES是一个基于python2.7搭建的流程，旨在从现存基因组中的保守基因组片段中重构祖先基因组图谱。它的输入文件最少是：一个标记了祖先节点的物种树和一组在现存物种中的同源markers，ANGES会计算每个物种对之间的保守基因组片段(即Ancestral Contiguous/Consecutive Sets, ACS)，并根据它们在现存基因组中的保守模式对其进行加权，然后利用Consecutive-Ones Property(C1P)性质将ACS组装成祖先染色体片段。ANGES可以重建多染色体线性基因组图谱(真核生物基因组)和单染色体环形基因组图谱(原核生物基因组)。
Tips：需要重构的祖先染色体基因组应与输入基因组是同一种类型，且Anges不能处理多个环形染色体基因组(比如具有染色体和质粒的原核生物基因组)
2.安装
#用conda构建python2.7环境并激活环境
conda create -n py27 python=2.7
conda activate py27
#使用wget或者git下载安装包
wget -c https://github.com/DyogenIBENS/Agora/archive/refs/heads/master.zip;unzip master.zip
git clone https://github.com/cchauve/ANGeS.git
3. 输入文件
3.1 物种树(必需输入)
#物种树必须是包含枝长的二叉树，内部节点无名称和注释，格式为NH或NHX格式
#用@来表示要推断祖先染色体的节点，下面的例子中就会推断Homo_sapiens和Pan_troglodytes的祖先染色体
((Homo_sapiens:0.01562,Pan_troglodytes:0.01562)@:0.0198250,Pongo_pygmaeus:0.03544);
3.2 markers(必需输入)
这部分输入文件需要注意的东西比较多：
1.两个不同的marker之间不能存在重叠，如果存在可以使用MARKERS/MARKERS_check_for_overlap_markers自行过滤
2.marker有两种处理方法，一种是根据用户标准提取子集，另一种是加倍；
3.marker的不同类型：
universal：marker在每个物种至少出现一次
unique：marker在在每个物种至多出现一次
ingroup-universal：marker在每个内群物种至少出现一次，但在外群部分物种缺失
ingroup-unique：marker在每个内群物种至多出现一次，但在外群部分物种出现多次
#marker的格式如下：
>marker_name
species.chromosome:start-end [+/-]
species.chromosome:start-end [+/-]
....
#marker_name必须为一个整数，species、chromosome物种名字和染色体各自名字中间不要有“.”
#chromosome后加一些描述性信息也可以，比如Homo_sapiens.1_X/Y:1246289-1887289 +
>1
Homo_sapiens.1:1246289-1887289 +
Pan_troglodytes.1:1238041-1835114 +
Pongo_pygmaeus.1:228608798-229274150 -
>2
Homo_sapiens.1:2330854-2704271 +
Pan_troglodytes.1:2293398-2879717 +
Pongo_pygmaeus.1:227893864-228155669 -
#如果你在marker1后面留了这个空行，后续都需要留这个空行
3.3 物种对文件格式(可选输入)
#每行两个物种，空格分隔
Homo_sapiens Pan_troglodytes
Homo_sapiens Pongo_pygmaeus
#基于上面输入的物种树结构，Pan_troglodytes和Pongo_pygmaeus信息对将不会被考虑在内
3.4 ACS文件格式(可选输入)
#ACS的格式如下：
id|weight;list_of_species:list of markers in the ACS
#id中不应该包含“ | ; , :”等特殊字符；一个ACS文件可以同时包含端粒marker和X-marker
1|0.5;Equus_caballus,Gallus_gallus,Homo_sapiens,Macaca_mulatta:1 2 3 4 5 6 7 8 9
2|0.225;Gallus_gallus,Homo_sapiens,Macaca_mulatta:1 2 3 4 5 6 7 8 9 T
3|1.0;Bos_taurus,Gallus_gallus,Taeniopygia_guttata:1 2 3 4 5 6 7 8
4|0.345;Canis_familiaris,Gallus_gallus:1 2 3 4 5 X 12 13
3.5 运行程序
conda activate py27
python /path/ANGeS/src/MASTER/anges_CAR.py PARAMETERS.file
4. 输出结果
4.1 输出目录
<EXP_DIR>/
├── INPUT/
│ ├── <ANCESTOR>_PARAMETERS # 参数文件
│ ├── <ANCESTOR>_SPECIES_TREE # 物种树文件
│ ├── <ANCESTOR>_MARKERS # 标记文件
│ ├── <ANCESTOR>_INFORMATIVE_PAIRS # 可选的用户提供的 informative pairs 文件。
│ └── <ANCESTOR>_ACS # 可选的用户提供的 ACS 文件。
│
├── MARKERS/
│ ├── <ANCESTOR>_MARKERS # 经过过滤的初始标记文件。
│ └── <ANCESTOR>_MARKERS_DOUBLED # 可选的加倍标记文件。
│
├── ACS/
│ ├── <ANCESTOR>_<ACS_TYPE>_<SPECIES1>_<SPECIES2> # 通过比较物种 <SPECIES1> 和 <SPECIES2> 得到的 ACS 文件，<ACS_TYPE> 可以是 SA（支持的邻接）、RA（可靠的邻接）、ACI（所有共同区间）、MCI（最大共同区间）或 SCI（强共同区间）
│ ├── <ANCESTOR>_ACS_<SPECIES1>_<SPECIES2> # 记录物种 <SPECIES1> 和 <SPECIES2> 之间所有 ACS 的文件。
│ ├── <ANCESTOR>_<ACS_TYPE>_<SPECIES1>_<SPECIES2>_MM1 # 如果missing marker采用方法1，则生成的附加文件。
│ ├── <ANCESTOR>_<ACS_TYPE>_<SPECIES1>_<SPECIES2>_MMX # 如果missing marker采用方法2，则生成的附加文件。
│ ├── <ANCESTOR>_<ACS_TYPE>_<SPECIES1>_<SPECIES2>_MM1X # 如果missing marker采用方法3，则生成的附加文件。
│ ├── <ANCESTOR>_<ACS_TYPE>_<SPECIES1>_<SPECIES2>_TEL # 如果添加了端粒 ACS，则生成的附加文件。
│ └── <ANCESTOR>_ACS # 包含所有 ACS 的文件（包括端粒 ACS）。
│
├── WEIGHT/
│ └── <ANCESTOR>_WACS # ACS 加权结果文件。
│
├── C1P/
│ ├── <ANCESTOR>_ACS_C1P_<METHOD> # 通过方法 <METHOD> 选择的保留 ACS 文件。<METHOD> 可以是BAB：分支定界法(branch-and-bound)、HEUR：贪心启发式算法(greedy heuristic)、SERIATION：谱排序法(spectral seriation)；如果考虑了端粒 ACS，则 <METHOD> 可以是TEL_BAB1(两阶段分支定界法)、TEL_BAB2(全局分支定界法)、TEL_HEUR(贪心启发式算法)
│ ├── <ANCESTOR>_ACS_DISC_<METHOD> # 通过方法 <METHOD> 选择的丢弃 ACS 文件。
│
├── CARS/
│ ├── <ANCESTOR>_PQRTREE # PQR 树文件，以初始标记表示。
│ ├── <ANCESTOR>_PQRTREE_DOUBLED # PQR 树文件，以加倍标记表示。
│ ├── <ANCESTOR>_PQTREE_<METHOD> # PQ 树文件，以初始标记表示，<METHOD> 同上。
│ └── <ANCESTOR>_PQTREE_DOUBLED_<METHOD> # PQ 树文件，以加倍标记表示，<METHOD> 同上。
│ # 所有文件遵循 CARs 文件格式。
│
└── ANCESTOR_LOG # 日志文件，记录 ANGES 运行的所有步骤（当使用图形界面运行时）。
4.2 CARs结果解读
最后的CARS使用PQR-tree(包括P节点、Q节点、R节点和C节点)表示，如_R、_Q、_C、_P表示节点的开始，R_、Q_、C_、P_表示节点的结束；R节点表示其中的ACS位置和顺序(方向)均不确定，Q节点表示其中的ACS位置和顺序(方向)均确定，C节点一般用作环形染色体，即首尾可以相接，P节点表示其中的ACS是连续的但是顺序(方向)不确定
#_Q 1 2 _P 4 6 _Q 3 7 8 Q_ P_ 5Q_；表示的所有的可能的组合有：
1 2 4 6 3 7 8 5, 1 2 4 6 8 7 3 5, 1 2 6 4 3 7 8 5, 1 2 6 4 8 7 3 5,
1 2 4 3 7 8 6 5, 1 2 4 8 7 3 6 5, 1 2 6 3 7 8 4 5, 1 2 6 8 7 3 4 5,
1 2 3 7 8 4 6 5, 1 2 8 7 3 4 6 5, 1 2 3 7 8 6 4 5, 1 2 8 7 3 6 4 5.
5. 绘图
先空着，有时间再搞
6. 相关的概念理解
6.1 ACS的组合模型
6.1.1 邻接
SA(supported adjacency)：两个marker在一个物种对中连续出现(无关顺序)，则成为支持邻接
RA(reliable adjacency)：如果一个邻接关系在三个输入基因组的进化路径上，且位于至少两个基因组的共同祖先中，并且该邻接关系在所有DCJ(Double-cut-and-joint)中位问题的解中都存在，则认定该邻接关系为可靠邻接
MA(marker adjacency)：当marker加倍后，初始marker(A)拆分成两个末端(A_head和A_tail)，由这两个末端组成的邻接关系(A_head-A_tail)叫做标记邻接
#RA计算的要求：marker必须同时具备unique和universal，且已经计算了SA
#环形基因组无法计算可靠邻接
6.1.2 线性基因组的公共区间
所有公共区间(all common interval，ACI)：在一个物种对中，两个或更多的marker以连续的方式出现(无关顺序)的集合
最大公共区间(maximal common intervals，MCI)：某一个公共区间至少出现一次且不被其它公共区间完全包含的公共区间
强共同区间(strong common intervals，SCI)：某一个公共区间至少出现一次且不与其它公共区间出现重叠的公共区间。重叠是指：两个公共区间的交集非空且没有一个并另一个完全包含
#环形基因组计算MCI和SCI的步骤：
#当marker是unique时,将环形基因组线性化，并保留它们共享的markerM，使用线性基因组的算法计算ACI，对于每个公共区间S，添加补集M-S，从ACI中找出MCI和SCI；
#当marker不是unique时，将每个环形基因组线性化后复制一份，使用线性基因组的算法计算ACI，并从ACI中找出MCI和SCI；
6.2 处理非universal markers
如果marker不是universal的，可能会出现以下情况：对于给定的物种对，某些marker在两个物种中均不出现或者在某一个基因组中不出现；
如果marker唯一，则先过滤两个物种基因组来保留仅在两个物种中都出现的marker，之后再过滤后的marker上计算ACS，而missing markers用以下四种方法处理：
如果marker不唯一，不会过滤，所以只有0和2可以被使用；
0：缺失标记被忽略，但是基于过滤后的marker计算的ACS不变
1：如果某个marker在其中一个基因组中的出现定义了一个包含另一个基因组中missing marker的基因组片段，则将该标记添加到ACS中，即Add markers spanned by intervals
2：所有marker在至少一个基因组中缺失被添加到ACS中作为特殊标记(X-marker)，即Add X’s
3：在两个基因组中都缺失的标记作为X-marker添加，而其中一个基因组中missing marker被公共区间S跨越时添加，即Add markers spanned by intervals and X’s
6.3 端粒ACS
对于给定的物种对，如果ACS在两个物种中出现的位置均位于染色体末端，则该ACS被认为是端粒ACS；
Tips：由于算法原因，ANGES不能同时处理包含端粒ACS和X-marker的ACS数据集
Tips：参数文件设置时，端粒ACS只能与unique marker一起使用
