title: Aligning coding sequences with frameshift extension penalties.
abstract: BACKGROUND
  Frameshift translation is an important phenomenon that contributes to the appearance of novel coding DNA sequences (CDS) and functions in gene evolution, by allowing alternative amino acid translations of gene coding regions. Frameshift translations can be identified by aligning two CDS, from a same gene or from homologous genes, while accounting for their codon structure. Two main classes of algorithms have been proposed to solve the problem of aligning CDS, either by amino acid sequence alignment back-translation, or by simultaneously accounting for the nucleotide and amino acid levels. The former does not allow to account for frameshift translations and up to now, the latter exclusively accounts for frameshift translation initiation, not considering the length of the translation disruption caused by a frameshift.
  
  
  RESULTS
  We introduce a new scoring scheme with an algorithm for the pairwise alignment of CDS accounting for frameshift translation initiation and length, while simultaneously considering nucleotide and amino acid sequences. The main specificity of the scoring scheme is the introduction of a penalty cost accounting for frameshift extension length to compute an adequate similarity score for a CDS alignment. The second specificity of the model is that the search space of the problem solved is the set of all feasible alignments between two CDS. Previous approaches have considered restricted search space or additional constraints on the decomposition of an alignment into length-3 sub-alignments. The algorithm described in this paper has the same asymptotic time complexity as the classical Needleman-Wunsch algorithm.
  
  
  CONCLUSIONS
  We compare the method to other CDS alignment methods based on an application to the comparison of pairs of CDS from homologoushuman,mouseandcowgenes of ten mammalian gene families from the Ensembl-Compara database. The results show that our method is particularly robust to parameter changes as compared to existing methods. It also appears to be a good compromise, performing well both in the presence and absence of frameshift translations. An implementation of the method is available at https://github.com/UdeS-CoBIUS/FsePSA.
authors.affiliation: Département d'informatique, Faculté des Sciences, Université de Sherbrooke, Sherbrooke, QC J1K2R1 Canada.
authors.forename: Safa
authors.identifier: 0000-0002-7709-1639
authors.initials: S
authors.lastname: Jammali
authors.affiliation: Département d'informatique, Faculté des Sciences, Université de Sherbrooke, Sherbrooke, QC J1K2R1 Canada.
authors.forename: Esaie
authors.initials: E
authors.lastname: Kuitche
authors.affiliation: Département d'informatique, Faculté des Sciences, Université de Sherbrooke, Sherbrooke, QC J1K2R1 Canada.
authors.forename: Ayoub
authors.initials: A
authors.lastname: Rachati
authors.affiliation: Département d'informatique, Faculté des Sciences, Université de Sherbrooke, Sherbrooke, QC J1K2R1 Canada.
authors.forename: François
authors.initials: F
authors.lastname: Bélanger
authors.affiliation: Département de biochimie, Faculté de médecine et des sciences de la santé, Université de Sherbrooke, Sherbrooke, QC J1E4K8 Canada.
authors.forename: Michelle
authors.initials: M
authors.lastname: Scott
authors.affiliation: Département d'informatique, Faculté des Sciences, Université de Sherbrooke, Sherbrooke, QC J1K2R1 Canada.
authors.forename: Aïda
authors.initials: A
authors.lastname: Ouangraoua
keywords: Coding DNA sequences pairwise alignment; Dynamic programming; Frameshifts