Here we present, for the first time, a frequentist progressive Multiple Sequence Alignment (MSA) method based on a rigorous and explicit mathematical formulation of insertions and deletions, namely the Poisson Indel Process (PIP). Having designed our algorithm in the Maximum Likelihood (ML) framework has enabled us to avoid the time-consuming Markov Chain Monte Carlo sampling of alignments. Our proposed algorithm aligns two homology paths, represented by their corresponding MSAs in polynomial time by ML under the PIP model (Maiolo et al. 2017). The procedure has been integrated into a progressive procedure that, traversing a given phylogenetic tree, produces at each internal node the optimal pairwise MSA ending at the root with the alignment of all the input sequences. The integration of PIP equations into a Dynamic Programming (DP) approach is not straightforward since the marginal likelihood is non-monotonic in the alignment length. Therefore, to account for the dependence on alignment length we have extended the DP matrices with a third dimension.
In order to reduce the computational complexity, the algorithm predicts candidate homologous segments for the purpose of filtering out non-promising regions in the DP matrix prior to the effective alignment process. Although our method has been strongly inspired by MAFFT, we have introduced a number of improvements like for example the use of a multi-scale short-time Fourier transform (STFT) for the automatic detection of candidate homologous patterns. Moreover, the use of the multiple-resolution STFT rather than the Fourier transform improves the detection of homologous regions especially in the presence of noise and in case of relative short patterns. We have also defined a more sophisticated and general approach to generate logically sound paths to connect homologous blocks and resolve overlaps between them.
To mitigate the intrinsic greediness brought by the progressive DP approach we have also implemented a Stochastic backtracking (Mueckstein et al. 2002) version of the algorithm under the PIP model. In this way, our progressive algorithm generates at each visited node a distribution of candidate sub-optimal alignments. Aligning sub-optimal solutions increases the chances to escape from local maxima and in our opinion provides a valid strategy to reduce the progressive bias.
Finally, to account for the among-sites substitution rate variation (ASRV) we have applied a Gamma distribution to all the rates, insertion and deletion rates included. However, further analysis are still needed to investigate the impact of ASRV on the inferred alignments. Our hope is that this feature could mimic to some extent a long insertion, that is, an insertion of more than a single character at a time.
The use of a sound mathematical model of indel, namely the Poisson Indel Process model, is providing more realistic and accurate estimates of MSAs, phylogenies and model parameters. As a consequence, our new algorithms will allow not only more accurate phylogeny and alignment inference but it will also facilitate the estimation of statistical supports of inferred tree partitions and the ancestral reconstruction of insertions-deletions and substitution history. Our tool has been developed in a user-friendly software package and is applicable to large genomic and metagenomic datasets.
--
Nous présentons ici, pour la première fois, une méthode d’alignement progressif de séquences multiples (MSA) basée sur une formulation mathématique rigoureuse et explicite des insertions et des suppressions, à savoir le procédé Poisson Indel (PIP). Le fait d’avoir conu notre algorithme dans le cadre du maximum de vraisemblance (ML) nous a permis d’éviter l’échantillonnage fastidieux des alignements par la chane de Markov Monte Carlo. L’algorithme que nous proposons aligne deux trajectoires homologiques, représentées par leurs MSA correspondantes en temps polynomial par ML sous le modèle PIP (Maiolo et al. 2017). La procédure a été intégrée dans une procédure progressive qui, en traversant un arbre phylogénétique donné, produit à chaque noeud interne le MSA optimal par paires se terminant à la racine avec l’alignement de toutes les séquences d’entrée. L’intégration des équations PIP dans une approche de programmation dynamique (DP) n’est pas simple puisque la probabilité marginale est non monotone dans la longueur de l’alignement. Par conséquent, pour tenir compte de la dépendance à la longueur d’alignement, nous avons étendu les matrices DP avec une troisième dimension.
Afin de réduire la complexité des calculs, l’algorithme prédit les segments homologues candidats afin de filtrer les régions non prometteuses dans la matrice DP avant le processus d’alignement efficace. Bien que notre méthode soit fortement inspirée du MAFFT, nous avons introduit un certain nombre d’améliorations comme par exemple l’utilisation d’une transformée de Fourier multi-échelle de courte durée (STFT) pour la détection automatique des modèles homologues candidats. De plus, l’utilisation de la STFT multirésolution plutt que de la transformée de Fourier améliore la détection des régions homologues, en particulier en présence de bruit et dans le cas de motifs relativement courts. Nous avons également défini une approche plus sophistiquée et plus générale pour générer des chemins logiquement sains pour connecter des blocs homologues et résoudre les chevauchements entre eux.
Pour atténuer l’avidité intrinsèque apportée par l’approche progressive de la PD, nous avons également mis en uvre une version rétrospective stochastique (Mueckstein et al. 2002) de l’algorithme selon le modèle PIP. De cette faon, notre algorithme progressif génère à chaque nud visité une distribution des alignements sous-optimaux candidats. L’alignement de solutions sous-optimales augmente les chances d’échapper aux maxima locaux et à notre avis, fournit une stratégie valable pour réduire le biais progressif.
Enfin, pour tenir compte de la variation du taux de substitution entre les sites (ASRV), nous avons appliqué une distribution gamma à tous les taux, taux d’insertion et de suppression inclus. Toutefois, une analyse plus approfondie est encore nécessaire pour étudier l’impact de l’ASRV sur les tracés déduits. Nous espérons que cette caractéristique pourrait imiter dans une certaine mesure une insertion ”longue”, c’est-à-dire une insertion de plus d’un caractère à la fois.
L’utilisation d’un modèle mathématique solide de l’indel, à savoir le modèle du processus de Poisson Indel, fournit des estimations plus réalistes et plus précises des ASM, des phylogénies et des paramètres du modèle. Par conséquent, nos nouveaux algorithmes permettront non seulement une phylogénie et une inférence d’alignement plus précises, mais ils faciliteront également l’estimation des supports statistiques des partitions d’arbres inférées et la reconstruction ancestrale des insertions-suppressions et de l’historique des substitutions. Notre outil a été développé dans un progiciel convivial et est applicable aux grands ensembles de données génomiques et métagénomiques.