Neural Time Warping for Multiple Sequence Alignment
Keisuke Kawano, Takuro Kutsuna, Satoshi Koide
Abstract
Multiple sequence alignment (MSA) is a traditional and still challenging task for time-series analyses. The MSA problem is intrinsically a discrete optimization and, in principle, dynamic programming is available for solving MSA. However, the computation complexity of such algorithms increases exponentially with the number of sequences to be aligned. In this paper, we propose neural time warping (NTW) that relaxes the original MSA to a continuous optimization, in which a neural network is used to model the alignment. We show that the solution of NTW is guaranteed to be a feasible solution of the original discrete problem under mild conditions. Our experimental results suggest that NTW successfully aligns a hundred sequences and significantly outperforms existing methods for solving the MSA problem.
BibTeX
@inproceedings{icassp2020_neuraltimewarpin,
title = {Neural Time Warping for Multiple Sequence Alignment},
author = {Keisuke Kawano and Takuro Kutsuna and Satoshi Koide},
booktitle = {ICASSP 2020},
year = {2020}
}