In this paper, we develop a new algorithm to construct Multiple and Global Alignments (MGA) of primary structures, i.e., strings coding biological macromolecules. The construction of such alignments is based on the one of the (longest)
Approximate Common Subsequences (ACS), made up by longer approximate substrings appearing, approximately, in the same positions in all the strings. This ACS represents a MGA. Constructing such
alignments is a way to find homologies between biological macromolecules. Our algorithm is of complexity O(N
2*L
2*(log(L))2) in computing time, where N is the number of the strings and L is the length of the longest string.
Keywords Strings - multiple and global alignments - common subsequence - divide-and-conquer strategy - algorithms - complexities