Please use this identifier to cite or link to this item:
https://doi.org/10.21256/zhaw-4775Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Maiolo, Massimo | - |
| dc.contributor.author | Zhang, Xiaolei | - |
| dc.contributor.author | Gil, Manuel | - |
| dc.contributor.author | Anisimova, Maria | - |
| dc.date.accessioned | 2019-01-22T14:31:56Z | - |
| dc.date.available | 2019-01-22T14:31:56Z | - |
| dc.date.issued | 2018 | - |
| dc.identifier.issn | 1471-2105 | de_CH |
| dc.identifier.uri | https://digitalcollection.zhaw.ch/handle/11475/14486 | - |
| dc.description.abstract | Background: Sequence alignment is crucial in genomics studies. However, optimal multiple sequence alignment (MSA) is NP-hard. Thus, modern MSA methods employ progressive heuristics, breaking the problem into a series of pairwise alignments guided by a phylogeny. Changes between homologous characters are typically modelled by a Markov substitution model. In contrast, the dynamics of indels are not modelled explicitly, because the computation of the marginal likelihood under such models has exponential time complexity in the number of taxa. But the failure to model indel evolution may lead to artificially short alignments due to biased indel placement, inconsistent with phylogenetic relationship. Results: Recently, the classical indel model TKF91 was modified to describe indel evolution on a phylogeny via a Poisson process, termed PIP. PIP allows to compute the joint marginal probability of an MSA and a tree in linear time. We present a new dynamic programming algorithm to align two MSAs –represented by the underlying homology paths– by full maximum likelihood under PIP in polynomial time, and apply it progressively along a guide tree. We have corroborated the correctness of our method by simulation, and compared it with competitive methods on an illustrative real dataset. Conclusions: Our MSA method is the first polynomial time progressive aligner with a rigorous mathematical formulation of indel evolution. The new method infers phylogenetically meaningful gap patterns alternative to the popular PRANK, while producing alignments of similar length. Moreover, the inferred gap patterns agree with what was predicted qualitatively by previous studies. The algorithm is implemented in a standalone C++ program. | de_CH |
| dc.language.iso | en | de_CH |
| dc.publisher | BioMed Central | de_CH |
| dc.relation.ispartof | BMC Bioinformatics | de_CH |
| dc.rights | http://creativecommons.org/licenses/by/4.0/ | de_CH |
| dc.subject | Dynamic programming | de_CH |
| dc.subject | Indel | de_CH |
| dc.subject | Phylogeny | de_CH |
| dc.subject | Poisson process | de_CH |
| dc.subject | Probability | de_CH |
| dc.subject | Sequence alignment | de_CH |
| dc.subject | Algorithms | de_CH |
| dc.subject | Molecular evolution | de_CH |
| dc.subject | INDEL mutation | de_CH |
| dc.subject.ddc | 572: Biochemie | de_CH |
| dc.title | Progressive multiple sequence alignment with indel evolution | de_CH |
| dc.type | Beitrag in wissenschaftlicher Zeitschrift | de_CH |
| dcterms.type | Text | de_CH |
| zhaw.departement | Life Sciences und Facility Management | de_CH |
| zhaw.organisationalunit | Institut für Computational Life Sciences (ICLS) | de_CH |
| dc.identifier.doi | 10.21256/zhaw-4775 | - |
| dc.identifier.doi | 10.1186/s12859-018-2357-1 | de_CH |
| dc.identifier.pmid | 30241460 | de_CH |
| zhaw.funding.eu | No | de_CH |
| zhaw.issue | 331 | de_CH |
| zhaw.originated.zhaw | Yes | de_CH |
| zhaw.publication.status | publishedVersion | de_CH |
| zhaw.volume | 19 | de_CH |
| zhaw.publication.review | Peer review (Publikation) | de_CH |
| zhaw.funding.snf | 31003A_157064 | de_CH |
| zhaw.webfeed | Computational Genomics | de_CH |
| zhaw.webfeed | Biomedical String Analysis | de_CH |
| Appears in collections: | Publikationen Life Sciences und Facility Management | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2018_Maiolo_Progressive multiple sequence alignment.pdf | 1.89 MB | Adobe PDF |  View/Open |
Show simple item record
Maiolo, M., Zhang, X., Gil, M., & Anisimova, M. (2018). Progressive multiple sequence alignment with indel evolution. BMC Bioinformatics, 19(331). https://doi.org/10.21256/zhaw-4775
Maiolo, M. et al. (2018) ‘Progressive multiple sequence alignment with indel evolution’, BMC Bioinformatics, 19(331). Available at: https://doi.org/10.21256/zhaw-4775.
M. Maiolo, X. Zhang, M. Gil, and M. Anisimova, “Progressive multiple sequence alignment with indel evolution,” BMC Bioinformatics, vol. 19, no. 331, 2018, doi: 10.21256/zhaw-4775.
MAIOLO, Massimo, Xiaolei ZHANG, Manuel GIL und Maria ANISIMOVA, 2018. Progressive multiple sequence alignment with indel evolution. BMC Bioinformatics. 2018. Bd. 19, Nr. 331. DOI 10.21256/zhaw-4775
Maiolo, Massimo, Xiaolei Zhang, Manuel Gil, and Maria Anisimova. 2018. “Progressive Multiple Sequence Alignment with Indel Evolution.” BMC Bioinformatics 19 (331). https://doi.org/10.21256/zhaw-4775.
Maiolo, Massimo, et al. “Progressive Multiple Sequence Alignment with Indel Evolution.” BMC Bioinformatics, vol. 19, no. 331, 2018, https://doi.org/10.21256/zhaw-4775.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.