Sequence analysis is a widespread approach to the study of contiguously ordered phenomena in the biological, social, and information sciences.
The most prominent example is in molecular biology where it has produced stunning results in the comparison of DNA, RNA, and protein sequences, leading to the genomic sequencing of whole organisms, and a commensurate increase in our understanding of evolution.
Sequence analysis has seen a wide range of applications in many areas of inquiry, including: stage theories for artifact and site dating in archeology; stage theories of economic and political development in political science; stage theories of child and moral development in psychology; sequential effects in perception, cognition, and learning in cognitive psychology; text collation, gaming algorithms, and recursive descent parsing of compiler grammars in computer science; market analysis and operations research in economics, and sequential equilibria in game theory; stratigraphic sequences in geology; numerous applications in linguistics; studies of interaction, the life course, and individual and institutional careers, among many others, in sociology, and so on.
The dynamic programming algorithm is a powerful approach to sequence comparison and is the most widely used approach today. Its only drawback has been high costs in computational complexity when the sequences being compared are either very long or very many. The linear algorithm substantially reduces these costs.
A short monograph describing the algorithm and an open source script implementing it are available at http://publicscience.net.
Pillar Communications is a private, Minneapolis-based Internet software company.