仙人掌图在基因组比较中的应用

### 仙人掌图在基因组比较中的应用 基因组比较在生物学研究中具有至关重要的意义。传统上，基因组比较在精细尺度上使用多序列比对，在大尺度上使用环形基因组图。然而，基因组之间的变化在许多中间水平上也呈现出复杂的嵌套结构，如小的倒位嵌套在大的倒位中，重复序列嵌套在重复序列中。为了捕捉这种嵌套结构，研究人员引入了一种名为仙人掌图的数据结构、分析和可视化方案。 #### 相关概念 - **块（Block）**：在基因组比较中，首先要识别和比对基因组之间及内部的同源DNA片段，这些片段的多序列比对被称为块。块是最大长度的同源字符串的最大集合，通过无间隙的比对来表示。具体来说，先形成一个由与给定碱基对同源的所有碱基对组成的列，然后在相邻碱基也都相互同源时，在左右两侧添加更多列。块中的水平行是代表在块中比对的同源DNA序列的字符串。 - **邻接（Adjacency）**：识别片段后，会留下未比对的DNA片段，这些片段被称为片段之间和染色体末端的邻接。为了使染色体两端的邻接成为合适的邻接，在每个末端添加一个代表端粒的帽，并通过邻接将这两个帽连接到第一个和最后一个片段。一般来说，帽可以是任何DNA序列的末端。 - **线程（Thread）**：线程是由交替的邻接和片段边组成的路径，其两侧是连接到帽的邻接。线程的潜在嵌套使得更容易表示被比较基因组染色体内的层次结构。 - **端（End）**：帽自然继承了定义它们的片段末端的同源性，对于染色体端粒可以预先定义额外的同源性，使得所有帽（无论是内部片段末端还是染色体端粒）都以相同的方式处理。一组同源帽被称为端。 #### 网络（Net） 网络是一种图，其中每个节点是一个端，每条边代表连接的两个端中的帽之间的一组邻接。用于比较一组基因组的完整网络为每个块的每个端和每个端粒端都有一个节点。只要在任何被比较的基因组中两个节点之间存在邻接，它们之间就有一条边。通常，节点排列在一个圆上，边是穿过圆的测地线。然而，随着基因组大小和基因组距离的增加，完整网络会变得非常密集且难以解释，幸运的是，它们通常可以分解为更小的组件。仙人掌图为从完整网络中提取更简单的子网和嵌套子结构提供了组织原则。 #### 仙人掌图（Cactus Graph） 仙人掌图的每个节点是完整网络的一个子网，每条边是一个块。仙人掌图由一组简单循环组成，任何两个简单循环最多在一个节点处相交，这使其具有“仙人掌状”外观。每个简单循环都有一个方向，决定了循环上每条边的方向。所有端粒端都包含在一个由称为原点的节点表示的子网中。通过递归定义，可以得到一个层次结构，称为仙人掌树，它由描述其子链相对顺序和方向的父子网以及这些链组成，每个链的链接中又包含一个描述嵌套在其中的进一步链的子网。这种层次结构代表了基因组之间在不同层次上共享的子结构的组织，从大的染色体区域到单个碱基。 #### 仙人