TrackMate 圈数追踪器

这里实现的线性分配问题（LAP）跟踪器遵循Jaqaman合作贡献的著名方法的专业版本及其¹。我们在这里重复参考论文中的想法，然后强调与表面实现的差异。

在TrackMate中，LAP框架备份跟踪器的两个实例（如果算上旧实例，则为4个，在v2.5.z之前）：

• 简单的圈数跟踪器；
• LAP追踪器。

第一个只是第二个简化版本：它的设置很少，仅处理不分裂也不合并的粒子，并忽略任何特征惩罚（见下文）。

这个跟踪器的所有成本都基于两个强氧化剂到强氧化剂的平方距离。如果用一句话来实现该跟踪器，则如下：简单的LAP跟踪器和LAP跟踪器非常适合进行布朗运动的强氧化剂。当然，只要强粒子不太密集，就它们适合非布朗运动。

粒子链接分两步进行：从一帧到一粒子链接创建跟踪片段，然后跟踪片段链接以实现间隙闭合。这两个步骤使用的数学公式是线性分配问题（LAP）：构建包含所有可能的分配成本矩阵。通过以最小总成本调查该矩阵来检索实际分配。我们首先描述如何排列成本矩阵，然后如何计算单个成本。

帧到帧链接的成本矩阵

第一步，检查两个连续帧的链接。第一帧的每个点都可以链接到下一帧中的任何其他点，或者不链接。它采用 (n+m) x (n+m) 矩阵的形状（n 是帧 t 中的点数，m 是帧 t+1 中的点数），可以分为 4 个象限。

• 左上象限（大小 n x m）包含将帧 t 中的点 i 链接到帧 t+1 中的任意点 j 的成本。
• 右上角象限（大小 n x n）包含帧 t 中的点 i 不与下一帧创建链接（产生段停止）的成本。
• 左下象限（大小 m x m）包含帧 t+1 中的点 j 不与前一帧有任何链接（段产生开始）的成本。
• 右下象限（大小m x n）是LAP形式在数学上所需的辅助。[^2]补充说明3给出了其存在的详细解释。该象限是通过对左上象限进行转置，将所有非阻塞成本块替换为最小成本来构建的。

工作站 LAP

为了解决这个LAP，我们依靠Munkres & Kuhn算法[^2]，它可以在时间表式期间解决问题(O(n³))。该算法返回最小化其总成本和的分配列表。

首先对所有帧对重复上述帧到帧链接。这产生了一系列非分支轨道段。轨道段可能由于缺少检测、或者由于合并或分裂事件而开始或停止，这个阶段不考虑这些。第二步需要提供轨道段与相互连接（而不仅仅是点），这将在下面进一步描述。

计算链接成本

在计算成本时，我们与 Jaqaman 等人¹ 的原始论文不同。在论文中，成本仅取决于点与点之间的距离，可能通过点强度的差异进行加权。这里，我们向用户提供通过增加现货功能的惩罚来调整成本，如下所述。

用户被要求提供最大允许链接距离（以物理单位输入），以及一系列点特征以及惩罚权重。这些参数用于调整成本矩阵。对于两个可能链接的点，链接成本计算如下：

1、计算两点之间的距离D 2.允许点之间的距离超过最大距离，则禁止链接，并且成本设置为infinity（即阻止值）。如果没有， 3.对于地图中的每个特征，惩罚p计算如下 \(p = 3 \times W \times \frac{ | f_1-f_2|}{f_1+f_2}\)
where W is the weight associated to the feature in the map. This expression is such that: - there is no penalty if the 2 feature values f1 and f2 are the same; - with a weight of 1, the penalty is 1 if one feature value is the double of the other; - the penalty is 2 if one feature value is 5 times largerr than the other one.

1. 将所有惩罚相加，形成 P = (1 + Σ p )
2. 成本设置为乘积的平方：C = ( D × P )²

如果用户不施加惩罚，则成本只是距离的平方。

计算非链接成本

帧到帧链路矩阵的右上和左下象限包含与轨道段终止或启动相关的成本（一个点不链接到下一帧或前一帧中的点）。这两个块中的每一个都是一个方阵，除了沿着对角线计算替代成本之外，到处都有块值。根据Jaqaman[^2]，该成本设置为

\[C_{替代} = 1.05 × 顶( C )\]

其中C是左上象限的成本。

成本计算和布朗运动

在没有惩罚且具有最大允许链接距离的情况下，返回的解决方案是最小化距离平方和的解决方案。这实际上对应于出现运动受Brownian motion控制的情况。例如参见 Crocker 和 Grier²。

通过添加特征惩罚，我们的目标是有利于相互“相似”的探针。在简单的单个探针连接问题中，点通常都是相同的，只是位置不同。然而，存在多种问题，这些特征惩罚可以增加跟踪过程的鲁棒性。

例如，我们最初开发了TrackMate，用于使用核细胞中的荧光DNA序列对非线虫细胞进行半自动谱系分析。正在分裂的细胞具有与分裂细胞非常不同的荧光DNA序列，这可以用于健康的跟踪。

轨道段链接

第二步，提供上面构建的轨道段以相互连接。Jaqaman 协同建议在此步骤中再次利用 LAP 框架。生成一个新的其成本矩阵，但这次考虑以下事件：

• 轨道段的终点可链接到任何轨道段的起点。这对应于间隙关闭事件，其中通常在被忽略分隔的其他两个点创建上链接。
• 轨道段的起点可链接到任何其他轨道段的中心部分（不是起点，也不是终点）的点。这对应于分割事件，其中轨道路径为两个子轨道。
• 轨道段的终止可链接到任何其他轨道段中央部分的点。这对应于合并事件，其中两个轨道合并为一个。我在生命科学领域还没有遇到过这种情况。
• 提供任何轨道段的点部分，不创建任何链接。

第二个成本矩阵的形状构成第一个成本矩阵，是为帧到帧链接而计算的，并且在原始文章中进行了最好的描述。

和以前一样，我们有了成本的计算方式，并重新使用了上述的特征惩罚框架。另外，用户必须在顶部提供链接的修改时间差，在该时间差上将提供链接。注意：这个最大时间以物理单位表示，而不是帧数。

与 Jaqaman 论文的主要区别

该论文的底层实现仍然是由 Khuloud Jaqaman 等人根据MATLAB开发并发表在《自然方法》上的实现。该软件名为 u-track，可以在 Khuloud Jaqaman homepage 上找到。

TrackMate 最初开发是为了简化§§12§§§C.elegans</i>谱系。因此，它只是捆绑了该框架的专业版本。

显着的差异是：

1. LAP框架是通用的：Jaqaman和同事提出了一个使用线性分配问题来近似多假设跟踪解决方案的框架。只需提供货架成本矩阵即可。TrackMate正确实现了LAP框架，但成本矩阵计算（针对每个问题）比u-track中的简单计算。 For instance, in TrackMate all link costs are based on the square distance between two spots (weighted or not by feature differences, see above), which make it tailored for Brownian motion. In u-track, the user is proposed with different motion types, including a linear motion whose parameters are determined on the fly. See for instance CD36 tracking, in the supplementary note 7 of the paper[9]. 2.在u-track中，计算的合并和分裂用于时间上和空间上重叠的两个粒子。这些事件的成本按两个粒子强度进行加权，以捕获正确由于描述重叠而导致的强度明显增加。 TrackMate中，我们使用分裂事件来描述细胞分裂，因为我们最初开发它是为了处理C.elegans谱系。然而，Jaqaman其同事似乎使用相同的方式来研究CD36解离和重新结合。
2. 在TrackMate中，距离和时间偏置由用户手动指定。在u-track中，它们是为每个粒子自动导出的，提供自适应。

参考文献

[^2]：J. Munkres，“分配和运输问题的算法”，工业与应用数学学会期刊，5(1):32–38，1957年3月