A New Approach for Multiple Sequence Alignment

We introduce a new multiple sequence alignment method for protein sequences. We name our method HSA (Horizontal Sequence Alignment) for it horizontally slides a window on the protein sequences simultaneously. 2 HSA is superior to the existing methods that depend on the order of proteins since we consider all the proteins at once. Unlike most of the existing multiple alignment methods, HSA takes secondary structure information into account to find a biologically relevant alignment. HSA uses a scoring matrix, such as BLOSUM 62 to capture substitution probabilities of amino acids. HSA runs in four steps: Step 1: (Initialization) We start by building a directed graph from the input proteins as follows. Each residue maps to a vertex in the graph. If it is available, Secondary Structure Element (SSE) type (α-helix, β-sheet) of each residue is also stored along with the vertex. A directed edge from vertex i to vertex j is added if residue j immediately follows residue i in the same sequence, or residues j and i have a substitution score higher than a given threshold. A weight is also assigned to each edge based on the substitution score and SSE type. If two residues belong to the same SSE type, then we assign a larger edge weight. All sequences are then scanned to find fragments with known SSE types. These fragments will guide the alignment later. The fragments are then clustered into groups, where each group consists of one fragment from every sequence, if they satisfy following four criterion: 1) They have same SSE type. 2) They have similar number of residues. 3) Their positions in th