对齐时间序列的高效基于对齐的平均延迟时间估计

to calculate the delay time averaged over all the aligned positions inall the minimum-cost alignments, which we call the mean time delay bythe minimum-cost alignments. You can enumerate all the minimum-costalignments and calculate their delay time at each aligned position oneby one, then average them. Unfortunately, this strategy is inefficientin the worst case because the number of the minimum-cost alignmentscan be exponential in the length of the time series.In this paper, we propose a method to calculate mean delay time bythe minimum-cost alignments in time and space linear in the number ofvertices in the minimum-cost alignment path graph, in addition to 𝑂(𝑇 2)time and space needed for length-𝑇 time series alignment. In the graphthat is composed of cells and minimum-cost edges between them inthe alignment cost table for dynamic programming, the minimum-costalignment path graph is the subgraph induced by the minimum-costalignment paths. Since each aligned position in the cost table corre-sponds to a diagonal edge on the path, delay time for each edge isadded only once by multiplying the number of the minimum-cost align-ment paths that pass through the edge in our method. Our numericalexperiments confirm computational efficiency and estimation accuracyof average delay time by our method.There are two major ways of aligning two sequences so as to matchthe corresponding positions. One is gap insertion, which is used inbioinformatics [8], and the other is DTW, which is used in speechrecognition [9]. For both ways, the minimum cost alignments areknown to be calculated efficiently using dynamic programming. Weshow the calculation method of our mean delay time for each wayconsidering their difference.0Array 15（2022）1002400放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。0ScienceDirect提供的内容列表0Array0期刊主页：www.elsevier.com/locate/array0波动延迟传播中的高效基于对齐的平均延迟时间估计0Atsuyoshi Nakamura �，Tatsuya Hayashi0日本北海道大学信息科学与技术研究生院0文章信息0关键词：对齐时间延迟估计动态时间扭曲 动态规划0摘要0我们提出了一种基于对齐的时间序列在时变延迟传播中的平均延迟时间估计算法。虽然最小成本对齐的数量可能与时间序列的长度成指数关系，但所提出的算法考虑了所有这样的对齐，并且作为后对齐处理，它在最小成本对齐图中的节点数量的时间内运行，这个时间最多是长度的平方。通过数值实验，我们的算法的效率得到了证实，与使用递归调用遍历图的朴素枚举算法相比。01. 引言0字符串或时间序列之间的对齐是它们之间的位置对应，而应用相关成本函数的最小成本对齐在许多领域中被使用，包括生物信息学和信号处理。尽管对齐的目的因其应用而异，但在这里，我们考虑将其用于时间序列之间的平均延迟时间估计。对于两个时间序列，对齐中对应位置的差异可以被视为一个时间序列相对于另一个时间序列的估计延迟，因此对齐可用于在时变延迟传播中估计它们之间的平均延迟时间。信号之间的时间延迟估计在声纳和雷达系统、地震学、地球物理学等领域得到了很好的研究。在这些领域的大多数研究中，通常假定瞬间的恒定延迟，并且交叉相关方法[2]是最广泛用于估计的方法。自那时以来，已经使用更现实的模型[3,4]和空间预测技术[5]进行了改进。对于时变时间延迟估计，已经在地震学研究领域提出了一种使用一种对齐的方法，称为DTW（动态时间扭曲）[6]。然而，在大量最小成本对齐路径的情况下，尚未考虑如何有效地计算平均时间延迟。当时间序列只能取有限值时，最小成本对齐通常是唯一的，但在这种情况下，可能存在许多这样的对齐。在这种情况下，我们可以计算所有最小成本对齐中所有对齐位置上的延迟时间的平均值，我们称之为最小成本对齐的平均时间延迟。您可以枚举所有最小成本对齐，并逐个计算它们的延迟时间，然后对它们进行平均。不幸的是，在最坏的情况下，这种策略是低效的，因为最小成本对齐的数量可能与时间序列的长度成指数关系。在本文中，我们提出了一种方法，用于在最小成本对齐路径图中的时间和空间中计算最小成本对齐的平均延迟时间，另外需要�（�2）的时间和空间来对长度为�的时间序列进行对齐。在由动态规划的对齐成本表中的单元格和它们之间的最小成本边组成的图中，最小成本对齐路径图是由最小成本对齐路径诱导的子图。由于成本表中的每个对齐位置对应于路径上的对角线边，因此在我们的方法中，每个边的延迟时间仅通过乘以通过该边的最小成本对齐路径的数量来添加一次。我们的数值实验证实了我们的方法的计算效率和延迟时间的估计精度。有两种主要的方法可以对两个序列进行对齐，以便匹配相应的位置。一种是插入间隙，用于生物信息学[8]，另一种是DTW，用于语音识别[9]。已知可以使用动态规划有效地计算最小成本对齐的两种方法。我们展示了考虑它们的差异的每种方法的平均延迟时间的计算方法。0� 通讯作者。电子邮件地址：atsu@ist.hokudai.ac.jp（A. Nakamura），thayashi@ist.hokudai.ac.jp（T.Hayashi）。0https://doi.org/10.1016/j.array.2022.100240收到日期：2022年2月12日；修订后收到日期：2022年7月19日；接受日期：2022年7月21日2(𝑠2[1], … , 𝑠2[10]) =(0, 1, 1, 0, −1, 1, 1, 1, 2, 0).(𝜋2(1), … , 𝜋2(10)) =(1, 2, 3, 4, 5, 7, 8, 9, 10, 11).𝑘123456789 10 11 12𝑠1[𝜋−11 (𝑘)]110 −1 −11120 −1𝑠2[𝜋−12 (𝑘)]0110 −111120𝑠′1[𝑘]1110 −1 −111120 −1𝑠′2[𝑘]0110 −1 −1111200𝑤(𝑠′1[𝑘], 𝑠′2[𝑘])100000000001𝜋−11 (𝑘)123456789 10𝜋−12 (𝑘)123456789 10𝜋−12 (𝑘) − 𝜋−11 (𝑘) 01110111≈ 0.754.𝑤(𝑥, 𝑦) =0((𝑥, 𝑦) = (0, 0), (1, 1))𝛼((𝑥, 𝑦) = (0, 1), (1, 0))(1)0Array 15 (2022) 1002400A. Nakamura and T. Hayashi0本文的组织如下。在第2节中，我们定义了最小成本对齐的平均延迟时间0最小成本对齐的延迟时间，并展示了基于间隙和基于变形成本的计算示例。提出了基于变形成本的有效计算方法，并针对我们引入的示例介绍了其过程，分析了时间和空间复杂性。在第3节中，我们展示了我们的计算方法的效率，通过数值实验与朴素计算方法进行比较。我们在第5节中总结了论文并描述了其未来方向。间隙成本的计算方法在附录中解释，以澄清两种成本之间计算的轻微差异。02. 最小成本对齐的平均延迟时间0对于任意自然数�，记号[�]表示集合{1，2，…，�}。0设�是R的子集。对于�=1，2，设��表示长度为�的时间序列，其第�个值为��[�]∈�，即，��=��[1]���[�]。让�表示位移函数对的集合，定义为从[�]到[2�−1]的严格增函数对(�1,�2)，使得�1([�])∪�2([�])是从1开始的连续自然数集合，即0�={ (�1,�2)∣��(1)<�<��(�)(�=1,2)，0�1([�])∪�2([�])=[max(�1([�])∪�2([�]))]}.0我们让�1表示由满足�1(1)=�2(1)=1的对(�1,�2)组成的�的子集。由位移函数对(�1,�2)∈�定义的�1和�2之间的对齐是指位置对应，其中�1[�−11(�)]对应于�2[�−12(�)]，对于�∈�1([�])∩�2([�])，其中�−1�0是��的逆函数。0主要有两种类型的对齐成本函数，基于变形的和基于间隙的。考虑值之间的成本函数�∶(�∪{�}0基于变形和基于间隙。考虑值之间的成本函数�∶(�∪{�})×(�∪{�})→�，其中�是对应于间隙的特殊值。然后，对齐成本�(�1,�2,(�1,�2))的定义为0�(�1,�2,(�1,�2))=∑0�∈�1([�])∪�2([�])�(�′1[�],�′2[�])。0在这里，对于�=1，2，0�′�[�]=��[�−1(�)]0在基于变形的成本中，其中�−1(�)=max{�∣��(�)≤�}，以及0�′�[�]0{��[�−1�(�)](�∈��([�]))0�（否则），0在基于间隙的成本中。请注意，�−1(�)=�−1(�)对于�∈�([�])。然后，�1和�2之间的齐成本为min(�1,�2)∈�1�(�1,�2,(�1,�2))，用于基于变形的成本，以及min(�1,�2))，用于基于间隙的成本。让��(�1,�2)表示所有最小成本对齐(�1,�2)之间的集合。然后通过最小成本对齐定义�1到�2的平均延迟时间为∑(�1,�2)∈��(�1,�2)∑�∈I(�1,�2)(�−12(�)−11(�))。0∑(�1,�2)∈��(�1,�2)|I(�1,�2)|，0其中，I(�1,�2)是一组对齐位置的集合，定义为�1([�])∩�2([�])�{1}，用于基于变形的，以及�1([�])∩�2([�])，用于基于间隙的成本。在下一节中，我们提出了一种有效的算法，用于通过最小成本对齐来计算平均延迟时间。0示例 1. 让 �  =  R  并考虑序列0( � 1 [1] ,  …  , � 1 [10]) =(1 ,  1 ,  0 ,  −1 ,  −1 ,  1 ,  1 ,  2 ,  0 ,−1) 以及0将成本函数 � 定义为  � ( �, � ) =  | �  −  � | ，并将移位函数 � 1 和 � 2 定义为0( � 1 (1) ,  …  , � 1 (10)) =(1 ,  3 ,  4 ,  5 ,  6 ,  7 ,  9 ,  10 ,  11 ,12) 以及0然后，由移位函数定义的 � 1 与  � 2 之间的对齐0对于这些对齐，( � 1 , � 2 ) 是具有最小变形成本的对齐之一0成本  2 . (请参阅下表。)0对于这个对齐，I( � 1 , � 2 ) = {3 ,  4 ,  5 ,  7 ,  9 ,  10 ,  11} 以及 ( ∑ � ∈I( � 1 ,� 2 )0( � −1 2 ( � ) −  � −1 1 ( � )) ,  | I( � 1 , � 2 ) | ) = (6 ,  7) . 考虑以下变化，0有 20 个对齐达到最小成本 2 和0( ∑ � ∈I( � 1 ,� 2 ) ( � −1 2 ( � ) −  � −1 1 ( � )) ,  | I( � 1 , � 2 ) | )  对于它们分别是 (4 ,  5)0(4 ,  6) 有 5 个对齐，(4 ,  7) 有 1 个对齐，(5 ,  6) 有 5 个对齐04×6 + 4×5 + 4×1 + 5×5 + 5×2 + 6×1 5×6 + 6×5 + 7×1 + 6×5 + 7×2 + 7×1  = 890� 2 从 � 1  的延迟时间通过最小成本的对齐是0示例 2. 让  �  = {0 ,  1}  并考虑序列  � 1  =001000100  和0� 2  = 000100010 . 对于 �  ≥  2 ，我们考虑时间序列 � 1  和0� � � � � ��01((�,)=(0,  ) , ( 0∞ (( �, � ) = (1 ,  � ) ,  ( � ,  1)( � ,  � )) .0强烈推荐序列与另一个序列中的值  1  对齐0在使用这个成本函数的对齐中，每个序列中的值 10( 2 ×  (位置差)  > � ) 或者字母  1  的数量不同。0序列，除非它们的位置差很大0对齐成本为  2 ，有  6  个对齐的对齐成本0考虑 � = 3 的情况。然后，基于最小间隙的0� 2 由移位函数定义为 ( � 1 (1) ,  …  , � 1 (9)) = (2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  10)0是最小的。 � 1 与0Array 15 (2022) 1002400并且 ( � 2 (1) ,  …  , � 2 (9)) = (1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  10) . (请参阅下表。)3A. Nakamura and T. Hayashi𝑘12345678910𝑠1[𝜋−11 (𝑘)]001000100𝑠2[𝜋−12 (𝑘)]000100010𝑠′1[𝑘]␣001000100𝑠′2[𝑘]00010001␣0𝑤(𝑠′1[𝑘], 𝑠′2[𝑘])1000000010𝜋−11 (𝑘)123456789𝜋−12 (𝑘)123456789𝜋−12 (𝑘) − 𝜋−11 (𝑘)11111110)= (7, 8).)(5, 8), (6, 8), (6, 8), (7, 8), (8, 8),===0� 1 2 3 4 5 6 7 8 9 100对于这种对齐，0I(�1,�2)={2,3,4,5,6,7,8,10}和(∑0�∈I(�1,�2)(�−12(�)−�−11(�))，|I(�1,�2)|0同样地，(∑0�∈I(�1,�2)(�−12(�)−�−11(�))，|I(�1,�2)|0其他最佳对齐的0因此，通过最小成本对齐，�2从�1的平均延迟时间为5+6×2+7×2+808×6=3903.高效计算0通过最小成本对齐计算平均延迟时间0当存在许多最小成本对齐时，计算两个序列之间的平均延迟时间是一项耗时的任务。针对这个问题，我们提出了一个快速算法。在本节中，我们解释了基于扭曲成本计算平均延迟时间的方法。请参阅附录0关于基于间隙成本计算平均延迟时间的方式。0首先，回顾使用动态规划进行最小成本对齐的常见计算算法。考虑两个时间序列�1=�1[1]��1[�]和�2=�2[1]��2[�]。记�(�1,�2)为�1[1]��1[�1]和�2[1]��2[�2]之间的(�1,�2)可以表示为以下递归公式。0�(�1,�2)0�0�(�1[1],�2[1])(�1=�2=1)0�(�1,�2−1)+�(�1[1],�2[�2])(�1=1,�2>1)0�(�1−1,�2)+�(�1[�1],�2[1])(�1>1,�2=1)0min{�(�1−1,�2),�(�1,�2−1),�(�1−1,�2−1)}0+�(�1[�1],�2[�2])(�1,�2>1)。0�(�,�)是�1和�2之间的最小对齐成本，可以通过按照(�1,�2)=(1,1)，…，(1,�)，(2,1)2,�)，�，(�,1)，…，(�,�)的顺序计算�(�1,�2)来计算。0考虑有向图�=(�,�)与0�={(�1,�2)∣�1,�2∈{1, … ,�} }0�={((�1,�2−1),(�1,�2))∣0�(�1,�2)=�(�1,�2−1)+�(�1[�1],�2[�2])}0∪{((�1−1,�2),(�1,�2))∣0�(�1,�2)=�(�1−1,�2)+�(�1[�1],�2[�2])}0∪{((�1−1,�2−1),(�1,�2))∣0�(�1,�2)=�(�1−1,�2−1)+�(�1[�1],�2[�2])}。0然后，从(1,1)到(�,�)的所有路径在�上对应于最小成本对齐。我们称这个图�(�,�)为�1和��之间的对齐路径图。我们还称由所有路径诱导的�的子图对应于最小成本对齐的最小成本对齐路径图，记为��(��,��)。0示例3.�1和�2的时间序列�的成本函数�(�,�)=0在示例1中，|�−�|及其对应的图�如图1所示。20个最小成本对齐对应于从(1,1)到(10,10)的路径在�上。0成本对齐，计算两个值足够了，∑(�1,�2)∈��(�1,�2)∑�∈I(�1,�2)(�−12(�)−�−11(�))和∑(�1,�2)∈��(�1,�2)|I(�1,�2)|。每个mini-0最小成本对齐(�1,�2)可以用路径表示0(�−11(1),�−12(1)),(�−11(2),�−12(2))，…，(�−11(�′),�−12(�′))0(�,�)在�中，其中0�′=max(�1(�)∪�2(�))。此外，对于�≥2，0�∈I(�1,�2)��−1�(�−1)+1=�−1�(�)对于�=1,20在�中，�(�1,�2)是从(�1,�2)到(�,�)的路径数，�(�1,�2)是从(1,1)到(�1,�2)的路径数。然后，包含边((�1−1,�2−1),(�1,�2))的最小成本对齐的数量�1,�2计算为�(�1−1,�2−1)�(�1,�2)。利用以上事实，∑(�1,�2)∈��(�1,�2)|I(�1,�2)|和∑(�1,�2)∈��(�1,�2)∑�∈I(�1,�2)(�−12(�)−0�−11(�))可以计算为0(�1,�2)∈��(�1,�2)|I(�1,�2)|0=0((�1−1,�2−1),(�1,�2))∈���(�1−1,�2−1)�(�1,�2)和0∑0,�2)0�∈I(�1,�2)(�−12(�)−�−11(�))0=0((�1−1,�2−1),(�1,�2))∈��(�2−�1)�(�1−1,�2−1)�(�1,�2)。0�(�1,�2)可以表示为以下递归公式：0�(�1,�2)0�01((�1,�2)=(�,�))01{((�1,�2),(�1,�2+1))∈�}�(�1,�2+1)(�1=�,�2<�)01{((�1,�2),(�1+1,�2))∈�}�(�1+1,�2)(�1<�,�2=�)01{((�1,�2),(�1,�2+1))∈�}�(�1,�2+1)0+1{((�1,�2),(�1+1,�2))∈�}�(�1+1,�2)0+1{((�1,�2),(�1+1,�2+1))∈�}�(�1+1,�2+1)(�1,�2<�)，0其中1{�}是一个指示函数，即1{�}=1，如果‘�’成立，否则为0。在��中，顶点(�1,�2)的�(�1,�2)可以通过从�(�,�)开始，并按照(�1,�2)的逆词典顺序计算�(�1,�2)来获得。0�(�1,�2)也可以用以下递归公式表示：0�(�1,�2)0�01((�1,�2)=(1,1))01{((�1,�2−1),(�1,�2))∈�}�(�1,�2−1)(�1=1,�2>1)01{((�1−1,�2),(�1,�2))∈�}�(�1−1,�2)(�1>1,�2=1)01{((�1,�2−1),(�1,�2))∈�}�(�1,�2−1)0+1{((�1−1,�2),(�1,�2))∈�}�(�1−1,�2)0+1{((�1−1,�2−1),(�1,�2))∈�}�(�1−1,�2−1)(�1,�2>1)，0在��中，顶点(�1,�2)的�(�1,�2)可以通过按照(�1,�2)的词典顺序计算�(�1,�2)来获得。4⎧⎪⎨⎪⎩𝛥𝑡 =⎧⎪⎪(2)0数组15（2022）1002400A. Nakamura and T. Hayashi0图1.在示例1中，对于时间序列�1和�2，其成本函数为�(�,�)=|�−�|，其对应的图�，以及最小成本路径上的�和�。从�上的路径从(1,1)到(10,10)的有向边是加粗的。仅在对应于最小成本对齐的路径中显示(�1,�2)的�(�1,�2)s和�(�1,�2)s，对于其他(�1,�2)为0，不需要计算。0示例4. 在示例1中，时间序列� 1 和� 2 的成本函数�(�,�) = |� -�|的�(�,�)和�(�,�)显示在图1中。从B和F中的值，∑(� 1,� 2)∈��(� 1,� 2)|I(� 1,� 2)| =2×1×5+3×4×5+2×4×1+2×20×1 = 118，以及∑(� 1,� 2)∈��(� 1,� 2)∑�∈I(� 1,� 2(�)−�−1 1(�)) =0×1×5+1×1×5+2×1×4×5+0×4×5+0×4×1+1×4×1+2×1×20×1 =89。因此，通过最小成本对齐的平均延迟时间为89∕118≈0.754，这与示例1中的计算一致。0表�和图�，这些都是非原始部分，可以在�（�2）的时间和空间内构建。其余的过程是通过最小成本对齐计算� 1 到� 2的平均延迟时间的原始部分。表�和�的构建在�（|��|）的时间和空间内完成。使用表计算∑(� 1,� 2)∈��(� 1,� 2)|I(� 1,� 2)|和∑(� 1,� 2)∈��(� 1,� 2)∑�∈I(� 1,� 2)(�1(�))也在�(|��|)的时间和空间内完成。因此，总体上，我们任务特定的其余部分可以在(|��|)的时间和空间内计算。使用�的递归公式进行的朴素计算可以通过递归调用来实现，但其时间复杂度线性依赖于最小成本对齐的数量，这可能对|��|呈指数增长。04. 数值实验04.1. 数据生成0我们生成100个整数序列对（� 1，� 2），每个长度� =100，200，…，1000，和噪声规模� =0（无噪声），如下所示。请注意，运算符%是模运算符。0� 1 [�]0{0（� = 1）0� 1 [� - 1] + � 1，�（� ≥ 2）0� 2 [�] 0� 2,�（� = 1）0� 2 [� - 1] + � 2，�（� = 2且� = 2）0� 1[� - ��] + ��（其他情况）0图2. 100个长度为100，…，1000的序列对的最小成本对齐路径图中最小成本路径和顶点的平均数量。0其中0� 1，1，…，� 1，�，� 2，1，� 2，2  � 在均匀分布上0{-50，-49，…，49，50}，0� 1，…，� �  � 在均匀分布上0{-50�，-50�-1，…，50�-1，50�}，01（� = 2且� = 1）02（� = 3且� = 2）0{� � −1  以0.9的概率取（（� = 3且� = 1）或� > 3）01 + (��−1%2) 以0.1的概率取（（� = 3且� = 1）或� > 3）0{�  =0{1 with prob. 0.90序列 � 1 是一个随机序列，其中 � 1 [1] = 0，两个连续项之间的差异遵循在 -50 到50 之间的整数集上的均匀分布。随机变量�，以0.9的概率取1，以0.1的概率取2，决定了 � 1 [1] 是否在 � = 2 或 � = 3时传播到 � 2，即如果 � = 1，则 � 2 [2] = � 1 [1]，如果 � = 2，则 � 2 [3] = � 1[1]。对于 � ≤ �，� 2 [1] 和 � 2 [�] - � 2 [� - 1]根据{-50，…，50}上的均匀分布生成。对于 � > �，� 2 [�] 取 � 1 [� - ��]，其中延迟时间 ��为1或2，��以0.9的概率取相同的值，以0.1的概率取不同的值。对于每个长度为100，…，1000的100个序列对，最小成本对齐路径图中的最小成本路径和顶点的数量被绘制在图2中。您可以看到顶点数量呈线性增长，但最小成本路径数量呈指数增长。我们还通过将噪声规模 �设置为0.1，0.2，…，1.0来生成100个长度为1000的嘈杂序列对，以检查平均延迟时间的估计精度。04.2. 实验设置0算法采用C++语言实现，并在Mac Pro (Late 2013)上执行（CPU：8核Intel(R)Xeon(R) E5-1680 v2 @ 3.00 GHz，内存：64 GB）。04.3. 结果0在计算所有最小成本路径的平均延迟时间时，我们比较了我们提出的方法与朴素深度优先搜索方法的计算效率。朴素深度优先方法通过以深度优先的方式遍历最小成本对齐路径图，从顶点（�，�）开始搜索所有最小成本对齐路径。50Array 15 (2022) 1002400A. Nakamura and T. Hayashi0图3.计算平均延迟时间的平均处理时间，由所提出的算法和朴素算法计算，序列对长度为100，…，1000。每个平均处理时间是在100个序列对上平均的。由于其耗时较长，我们放弃了对长度为900和1000的序列对使用朴素算法进行处理时间测量。0图4. 所提出的算法和朴素算法的散点图（最小成本路径数，处理时间）0图5. 所提算法的散点图（最小成本对齐路径图中顶点数，处理时间）0结果如图3所示。我们提出的算法的平均处理时间接近线性增加，而朴素算法的处理时间呈指数增长。它们之间的关系看起来类似于顶点数和最小成本对齐路径数之间的关系。事实上，朴素算法的处理时间随着最小成本对齐路径数的增加而线性增加，尽管该数量不影响处理时间。0图6. 所提算法在噪声尺度 � = 0.1，…，1.0 的平均误差率0如图4的散点图所示，所提出的算法的顶点数量几乎呈线性依赖关系。最后，我们检查了所提出方法估计的平均延迟时间的准确性。平均延迟时间的真实值定义为由方程（2）生成的 � � 平均值，� = � +1，…，�。其误差率定义为估计平均延迟时间与真实平均延迟时间的绝对差除以真实平均延迟时间。噪声尺度为� =0，0.1，0.2，…，1.0的1000个长度序列对的平均误差率如图6所示。可以看到，即使噪声宽度与波动宽度相同（� = 1.0），误差率也非常小，甚至低于7%。05. 结论和未来工作0所提出的基于对齐的平均延迟时间估计算法在具有大量最小成本对齐的情况下非常高效；其计算时间（不包括对齐时间）随着最小成本对齐路径图中节点数的增加而线性增加，最多为时间序列长度的平方，而最小成本对齐的数量可能是指数级的。在我们的数值实验中，长度为1000的时间序列之间的最小成本对齐数量平均超过十亿，这表明在某些应用中我们不能忽视大量最小成本对齐的问题。我们的方法也可以应用于延迟时间波动剧烈的时间序列，如股价和销售历史，因此在数据挖掘中使用它可能是有趣的。事实上，我们在本文中开发的技术已经在股价和细胞放电分析的传播图的边集估计应用中使用[10]。我们现在正在考虑将我们的方法应用于各种其他领域的可能性。0CRediT作者贡献声明0Atsuyoshi Nakamura:  概念化，方法论，软件，撰写。  Tatsuya Hayashi:方法论，软件。01论文[10]侧重于如何使用时间延迟和（未除以对齐位置数的平均延迟时间）来估计传播图中的有向边，但没有描述如何高效地计算它。Array 15 (2022) 1002406A. Nakamura and T. Hayashi𝐷(𝑡1, 𝑡2)=⎧⎪⎪⎪⎪⎨⎪⎪0(𝑡1 = 𝑡2 = 0)𝐷(𝑡1, 𝑡2 − 1) + 𝑤(␣, 𝑐2[𝑡2])(𝑡1 = 0, 𝑡2 > 0)𝐷(𝑡1 − 1, 𝑡2) + 𝑤(𝑐1[𝑡1], ␣)(𝑡1 > 0, 𝑡2 = 0)⎧⎪⎨𝐷(𝑡1 − 1, 𝑡2) + 𝑤(𝑐1[𝑡1], ␣)𝐷(𝑡1, 𝑡2 − 1) + 𝑤(␣, 𝑐2[𝑡2])𝐷(𝑡1 − 1, 𝑡2 − 1) + 𝑤(𝑐1[𝑡1], 𝑐2[𝑡2])⎫⎪⎬(𝑡1, 𝑡2 > 0).𝑉 ={(𝑡1, 𝑡2) ∣ 𝑡1, 𝑡2 ∈ {0, 1, … , 𝑇 }}𝐸 = {((𝑡1, 𝑡2 − 1), (𝑡1, 𝑡2)) ∣ 𝐷(𝑡1, 𝑡2) = 𝐷(𝑡1, 𝑡2 − 1) + 𝑤(␣, 𝑐2[𝑡2])}∪{((𝑡1 − 1, 𝑡2), (𝑡1, 𝑡2)) ∣ 𝐷(𝑡1, 𝑡2) = 𝐷(𝑡1 − 1, 𝑡2) + 𝑤(𝑐1[𝑡1], ␣)}∪{((𝑡1 − 1, 𝑡2 − 1), (𝑡1, 𝑡2)) ∣ 𝐷(𝑡1, 𝑡2) = 𝐷(𝑡1 − 1, 𝑡2) + 𝑤(𝑐1[𝑡1], 𝑐2[𝑡2])}.𝐹(𝑡1, 𝑡2)=⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩1((𝑡1, 𝑡2) = (0, 0))1{((𝑡1, 𝑡2−1), (𝑡1, 𝑡2))∈𝐸}𝐹(𝑡1, 𝑡2−1)(𝑡1 =0, 𝑡2 > 0)1{((𝑡1 − 1, 𝑡2), (𝑡1, 𝑡2))∈𝐸}𝐹(𝑡1−1, 𝑡2)(𝑡1 >0, 𝑡2 =0)1{((𝑡1, 𝑡2−1), (𝑡1, 𝑡2))∈𝐸}𝐹(𝑡1, 𝑡2−1)= 0.8125,0利益声明0本文的一名或多名作者已披露潜在的或相关的利益冲突。0与本工作可能存在潜在利益冲突的相关冲突，可能包括直接或间接的付款、机构支持或与生物医学领域的实体关联，这可能被视为与本工作存在潜在利益冲突。有关完整的披露声明，请参阅 https://doi.org/10.1016/j.array.2022.100240。Atsuyoshi Naka- mura报告称日本学术振兴会提供了财务支持。0致谢0我们要感谢堀川和民木教授。0小林教授对我们进行了研究的激励。本工作得到了JSPS KAKENHI GrantNumber JP18H05413的支持。0附录。基于间隙成本的平均延迟时间计算0在两个序列  � 1  和  � 2 的对齐中，基于配准的成本要求  � 1  或  � 2中的一个不能是空时间序列，但基于间隙的成本则要求  � 1 和  � 2都可以是空时间序列。因此，需要计算  � 1  = 0  或  � 2  = 0 时的最小对齐成本  � ( �1 , � 2 ) ，其中  � 1 [1]  �  � 1 [0] 表示空时间序列。基于间隙成本的  � ( � 1 , � 2 )的递归公式如下：0最小值0代表最小成本对齐的有向图  � ( � , � )  可以构建如下0所有从(0, 0)到( � , �  )的路径都对应于最小成本的对齐。从( � 1 , � 2 )到( � , �)的路径数可以用与基于配准的成本相同的递归公式表示。 � ( � 1 , � 2 )的递归公式是0+ 1 {((�1−1，�2)，(�1，�2))∈�}�(�1−1，�2)0+ 1 {((�1−1，�2−1)，(�1，�2))∈�}�(�1−1，�2−1)(�1，�2>0)。0图A.7。对于时间序列�1和�2，成本函数为(1)，在示例2中设置�=3，其对应的图�，以及最小成本路径上的�和�。在从(0，0)到(9，9)的路径中的有向边是加粗的。需要计算最小成本对齐对应的路径中(�1，�2)的�(�1，�2)和�(�1，�2)。0示例5。对于时间序列�1和�2，成本函数为(1)，在示例2中设置�=3，其对应的图�，从(�1，�2)到(9，9)的路径数�(�1，�2)和从(0，0)到(�1，�2)的最小成本路径上的路径数�(�1，�2)在图A.7中显示。最小成本对齐对应于从(0，0)到(9，9)的路径。从B和F中的值，我们可以通过最小成本对齐计算平均延迟时间为00 × 1 × 4 + 0 × 1 × 2 + 1 × 1 × 2 + 1 × 2 × 201 × 4 + 2 × 1 × 2 + 2 × 2 + 5 × 3 × 2 + 3 × 1 + 3 × 1  =390这与示例2中的计算相符。0参考文献0[1]  陈J，黄Y，Benesty J。时间延迟估计。在：黄Y，Benesty J，0编辑。下一代多媒体通信系统的音频信号处理。Norwell, MA: Kluwer; 2004, p. 197–227。0[2] Knapp C，Carter G。用于时间估计的广义相关方法0延迟。IEEE Trans Acoust Speech Signal Process1976;24(4):320–7。http://dx.doi.org/10.1109/TASSP.1976.1162830。0[3] Manickam T，Vaccaro R，Tufts D。用于多径时间-的最小二乘算法0延迟估计。IEEE Trans Signal Process1994;42(11):3229–33。http://dx.doi.org/10.1109/78.330381。0[4] Benesty J。被动声学源定位的自适应特征值分解算法0源定位。J Acoust Soc Am 2000;107(1):384–91。http://dx.doi.org/10. 1121/1.428310。0[5]  Haykin S。用于到达角度估计的雷达阵列处理。在：阵列信号0处理（A85-43960 21-32）。恩格尔伍德克利夫斯。1985, p. 194–292。0[6] 迫江H，千叶S。口语识别的动态规划算法优化0词语识别。IEEE Trans Acoust Speech Signal Process1978;26(1):43–9。http://dx.doi.org/10.1109/TASSP.1978.1163055。70数组15（2022）1002400A.中村和T.林田0[7] Hale D。地震图像的动态弯曲。地球物理学2013;78(2):S105–15。0http://dx.doi.org/10.1190/geo2012-0327.1。0[8]  Mount DW。生物信息学-序列和基因组分析。第二版。Cold Spring0港实验室出版社; 2004。0[9]  阮B-H。关于语音识别的隐马尔可夫模型和动态时间弯曲0识别-统一观点。AT&T贝尔实验室技术杂志1984;63(7):1213–43。0[10] 林田T，中村A。从个体的时间推断图估计0观察状态的系列。科学报告2022;12(