Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.21256/zhaw-20794| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | Accelerating phylogeny-aware alignment with indel evolution using short time Fourier transform |
| Autor/-in: | Maiolo, Massimo Ulzega, Simone Gil, Manuel Anisimova, Maria |
| et. al: | No |
| DOI: | 10.1093/nargab/lqaa092 10.21256/zhaw-20794 |
| Erschienen in: | NAR Genomics and Bioinformatics |
| Band(Heft): | 2 |
| Heft: | 4 |
| Seite(n): | lqaa092 |
| Erscheinungsdatum: | 6-Nov-2020 |
| Verlag / Hrsg. Institution: | Oxford University Press |
| ISSN: | 2631-9268 |
| Sprache: | Englisch |
| Fachgebiet (DDC): | 510: Mathematik 572: Biochemie |
| Zusammenfassung: | Recently we presented a frequentist dynamic pro- gramming (DP) approach for multiple sequence alignment based on the explicit model of indel evolution Poisson Indel Process (PIP). This phylogeny-aware approach produces evolutionary meaningful gap patterns and is robust to the ‘over-alignment’ bias. Despite linear time complexity for the computation of marginal likelihoods, the overall method’s complexity is cubic in sequence length. Inspired by the popular aligner MAFFT, we propose a new technique to accelerate the evolutionary indel based alignment. Amino acid sequences are converted to sequences representing their physicochemical properties, and homologous blocks are identified by multi-scale short-time Fourier transform. Three three-dimensional DP matrices are then created under PIP, with homologous blocks defining sparse structures where most cells are excluded from the calculations. The homologous blocks are connected through intermediate ‘linking blocks’. The homologous and linking blocks are aligned under PIP as independent DP sub-matrices and their tracebacks merged to yield the final alignment. The new algorithm can largely profit from parallel computing, yielding a theoretical speed-up estimated to be pro- portional to the cubic power of the number of sub-blocks in the DP matrices. We compare the new method to the original PIP approach and demonstrate it on real data. |
| URI: | https://digitalcollection.zhaw.ch/handle/11475/20794 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | CC BY-NC 4.0: Namensnennung - Nicht kommerziell 4.0 International |
| Departement: | Life Sciences und Facility Management |
| Organisationseinheit: | Institut für Computational Life Sciences (ICLS) |
| Publiziert im Rahmen des ZHAW-Projekts: | Fast joint estimation of alignment and phylogeny from genomics sequences in a frequentist framework |
| Enthalten in den Sammlungen: | Publikationen Life Sciences und Facility Management |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| 2020_Maiolo-etal_Accelerating-phylogeny-aware-alignment-indel-evolution.pdf | 1.83 MB | Adobe PDF |  Öffnen/Anzeigen |
Zur Langanzeige
Maiolo, M., Ulzega, S., Gil, M., & Anisimova, M. (2020). Accelerating phylogeny-aware alignment with indel evolution using short time Fourier transform. NAR Genomics and Bioinformatics, 2(4), lqaa092. https://doi.org/10.1093/nargab/lqaa092
Maiolo, M. et al. (2020) ‘Accelerating phylogeny-aware alignment with indel evolution using short time Fourier transform’, NAR Genomics and Bioinformatics, 2(4), p. lqaa092. Available at: https://doi.org/10.1093/nargab/lqaa092.
M. Maiolo, S. Ulzega, M. Gil, and M. Anisimova, “Accelerating phylogeny-aware alignment with indel evolution using short time Fourier transform,” NAR Genomics and Bioinformatics, vol. 2, no. 4, p. lqaa092, Nov. 2020, doi: 10.1093/nargab/lqaa092.
MAIOLO, Massimo, Simone ULZEGA, Manuel GIL und Maria ANISIMOVA, 2020. Accelerating phylogeny-aware alignment with indel evolution using short time Fourier transform. NAR Genomics and Bioinformatics. 6 November 2020. Bd. 2, Nr. 4, S. lqaa092. DOI 10.1093/nargab/lqaa092
Maiolo, Massimo, Simone Ulzega, Manuel Gil, and Maria Anisimova. 2020. “Accelerating Phylogeny-Aware Alignment with Indel Evolution Using Short Time Fourier Transform.” NAR Genomics and Bioinformatics 2 (4): lqaa092. https://doi.org/10.1093/nargab/lqaa092.
Maiolo, Massimo, et al. “Accelerating Phylogeny-Aware Alignment with Indel Evolution Using Short Time Fourier Transform.” NAR Genomics and Bioinformatics, vol. 2, no. 4, Nov. 2020, p. lqaa092, https://doi.org/10.1093/nargab/lqaa092.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.