Pattern recognition in several sequences: Consensus and alignment (Q1059004)

This paper gives a practical algorithm to determine the consensus alignment of several sequences. In biology, this problem is central to determination of secondary and tertiary structures and functional significance of subsequences in DNA or proteins. The computation required for the algorithm is (loosely speaking) O(rn), where r is the number of sequences and n is the length of the sequences, rather than the usual \(O(n^ r)\) of dynamic programming algorithms. The algorithm can find unknown consensus sequences and search for homologues of a known functional sequence. A discussion of statistical significance of the results is also included. In particular, the algorithm is applicable to the search for mutational ''hotspots'', and promoter and regulatory regions in DNA, as well as binding sites for repressor proteins and hormones.