title: Gap mapping: a paradigm for aligning two sequences.
abstract: Pairwise sequence alignment is one of the most essential tools in comparative genomic sequence analysis. It is used to compare the sequences of genes and proteins with the aim of inferring structural, functional and evolutionary relationships. However, current 'mainstream' alignment algorithms have optimisation criteria based primarily on computational efficiency using parameters such as gap penalties, which are not biologically motivated. In addition, current alignment algorithms such as the Smith and Waterman technique provide a single alignment that could be sensitive to rather arbitrary choices in parameters such as gap penalties. This paper explores the range of properties resulting from posing the alignment problem more as a 'mapping gaps in sequences' exercise. We argue that this approach is intuitive and provides greater control over the number of gaps placed within an alignment. This type of approach was proposed by Sankoff (1972), but unfortunately has not received much attention. We report and discuss our findings by comparing this approach to other techniques using structurally confirmed aligned sequences from a benchmark alignment database. Interestingly, this approach consistently provides optimal and near optimal alignments and is thus a viable approach to sequence alignment.
authors.affiliation: Centre for Bioinformatics and Biological Computing, School of Information Technology, Murdoch University, WA, Australia. m.bellgard@murdoch.edu.au
authors.forename: Matthew
authors.initials: M
authors.lastname: Bellgard
authors.forename: Thomas
authors.initials: T
authors.lastname: Gamble
authors.forename: Mark
authors.initials: M
authors.lastname: Reynolds
authors.forename: Adam
authors.initials: A
authors.lastname: Hunter
authors.forename: Ed
authors.initials: E
authors.lastname: Trifonov
authors.forename: Ross
authors.initials: R
authors.lastname: Taplin
mesh_terms: D000465:Algorithms; D020869:Gene Expression Profiling / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology