Exact and Heuristic Algorithms for the Indel Maximum Likelihood Problem

Diallo, Abdoulaye Banire; Makarenkov, Vladimir et Blanchette, Mathieu (2007). « Exact and Heuristic Algorithms for the Indel Maximum Likelihood Problem ». Journal of Computational Biology, 14(4), pp. 446-461.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (429kB)

Résumé

Given a multiple alignment of orthologous DNA sequences and a phylogenetic tree for these sequences, we investigate the problem of reconstructing the most likely scenario of insertions and deletions capable of explaining the gaps observed in the alignment. This problem, that we called the Indel Maximum Likelihood Problem (IMLP), is an important step toward the reconstruction of ancestral genomics sequences, and is important for studying evolutionary processes, genome function, adaptation and convergence. We solve the IMLP using a new type of tree hidden Markov model whose states correspond to single-base evolutionary scenarios and where transitions model dependencies between neighboring columns. The standard Viterbi and Forward-backward algorithms are optimized to produce the most likely ancestral reconstruction and to compute the level of confidence associated to specific regions of the reconstruction. A heuristic is presented to make the method practical for large data sets, while retaining an extremely high degree of accuracy. The methods are illustrated on a 1Mb alignment of the CFTR regions from 12 mammals.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	Ancestral genome reconstruction; Insertions and deletions; Tree-HMM; Ancestral mammalian genomes, indel maximum likelihood problem
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	Vladimir Makarenkov
Date de dépôt:	23 mars 2016 13:17
Dernière modification:	20 avr. 2016 19:59
Adresse URL :	http://archipel.uqam.ca/id/eprint/8013

Modifier les métadonnées (propriétaire du document)

Statistiques