长度分布悬殊的序列比对法

Sequence Alignment Method with Large Length Distribution

经典的动态时间规整算法(Dynamic Time Warping,DTW)对长度相差剧烈的两个序列之间的相异(似)性度量会引入长度的影响,这种影响在多对序列之间匹配时造成度量数值上的失衡从而导致DTW度量相似性的失效.该文分析了这种失效性的来源,提出祛除长度差异影响的均值DTW法.和传统DTW法相比,均值DTW是其非平凡的推广,因而无法直接使用基于动态规划原理的算法.基于该文给出的动态规划的匹配路径数目计算,强调了枚举法施加于均值DTW的不可行性.在引入均值的累计计算技巧后,将均值DTW纳入传统的基于动态规划原理的算法框架,实现了等价于DTW计算复杂性、双倍于DTW存储占用的均值DTW算法.该算法相比于DTW在电离辐射时间序列的聚类实验中将算法结果的精度指标至少提升了50%以上.该文的创新性在于:1)首次发现了DTW可能失效的长度差异因素; 2)提出了均值DTW的概念; 3)首次提出了动态路径数目的定量计算方法; 4)给出均值DTW的加窗限制版本.

The classic Dynamic Time Warping( DTW) method introduces the effect of length on the difference( similarity) between two sequences with severe length differences. This effect can cause measurement problems when matching between multiple pairs of sequences. The numerical imbalance leads to the failure of the DTW metric similarity. This paper analyzes the source of this failure and proposes the mean DTW method to eliminate the influence of length difference. Compared with the traditional DTW method,the mean DTW is a non-trivial promotion,so it is impossible to directly use the algorithm based on the dynamic programming principle. Based on the calculation of the number of all matching paths for dynamic programming given in this paper,the infeasibility of the enumeration method applied to the mean DTW is emphasized. After introducing the cumulative calculation technique of the mean,the mean DTW is included in the traditional algorithm framework based on the dynamic programming principle,and the mean DTW algorithm equivalent to DTW computational complexity and double the DTW storage occupancy is realized. Compared with DTW,the algorithm improves the accuracy of the algorithm results by at least 50% in the clustering experiment of ionizing radiation time series. The innovation of this paper is: 1) the first time to find the difference in length of DTW possible failure;2) the concept of mean DTW is proposed;3) the quantitative calculation method of the number of dynamic paths is proposed for the first time;4) the addition of the mean DTW is given,windowlimited version.