Peak Alignment using Restricted Edit Distances
Veli Mäkinen
A peak is a pair of real values (x, y), where x is the time when peak of height y is
registered. In the peak alignment problem, we are given two sequences of peaks, and
our task is to align the sequences allowing some basic edit operations on the peaks.
We study an instance of the peak alignment problem that arises in the analysis
of Mass Spectrometry data in Systems Biology. There the measurement technique
guarantees that two peaks (x, y), (x', y') can only be considered the same if x is
close enough to x', and y is close enough to y'. We review some methods to do
alignment under such restrictions on matches.
Key words: mass spectrometry, gel electrophoresis, peak alignment, edit distance,
sparse dynamic programming