Mind the gaps: Progress in progressive alignment

Abstract

he article by Lo¨ytynoja andGoldman (1) in this issue ofPNAS describes a novel anduseful method of handling gapsin progressive multiple sequence align-ments. Gaps are the bits that get leftbehind when you try to align DNA orprotein sequences and have to use pad-ding or null characters to match homol-ogous residues. These could get placedat sites where one sequence has appar-ently lost some residues (caused by adeletion), and you simply pad out thesequence with gap characters such ashyphens or blanks to make it match upwith the sequences that have not lostanything. Similarly, if one or moresequences have some extra residues(caused by an insertion) then these willneed to be matched by gap characters inthe other sequences. It is the placementof these gaps that creates all of theproblems when you try to automaticallygenerate alignments. If insertions anddeletions never happened, then se-quences could easily be matched by slid-ing them past each other and taking thealignment that best matched the resi-dues. When gaps are needed, things getcomplicated and much of the first 20years of bioinformatics was devoted tohow these should be placed and why(e.g., refs. 2–4).When you have just two sequences,there are fast and relatively simple algo-rithms that can guarantee the best align-ment between the sequences, given ascoring function that gives a score foreach pair of aligned residues. The mostfamiliar of these is the famous dynamicprogramming algorithm, first describedfor sequence alignment by Needlemanand Wunsch (5). Gaps can be placed allover both sequences to get the bestscore so a ‘‘gap penalty’’ function isused to penalize for gaps of differentsizes. These scores are used to give abalance between gaps and matches. Inan ideal world, if you use appropriatevalues for the residue match scores suchas from a

Keywords

Affiliated Institutions

• University College Dublin IE

Related Publications