View Related Documents

Abstract

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

Fulltext Preview

Image of the first page of the fulltext document