Temporal Needleman-Wunsch

The Needleman-Wunsch algorithm (NW) marked the genesis of a new field of research known as sequence alignment. Its inception was motivated by the growing need for automated methods to find homologous biological sequences. Subsequently, sequence alignment has established itself as a standard approach in bioinformatics, and has also been applied to other domains, including sequences of temporal events. Little prior work has been undertaken on alignment methods in using the temporal information associated with event sequences. In this manuscript, we propose the Temporal Needleman-Wunsch (TNW) algorithm, which modifies the NW approach in a principled manner to use time between events for scoring an alignment. To the best of our knowledge, this is the first formal temporal-extension of a global alignment algorithm. We show that the modification can also be used with the Smith-Waterman algorithm that performs local sequence alignment. We introduce an efficient implementation strategy for the TNW that ensures that the time-complexity is not worse than the NW. We test the abilities of the TNW on event-log data from Electronic Medical Records to identify treatment protocols and to cluster patients based on sequence similarity.