| 1. |
- Addario-Berry, L, et al.
(författare)
-
Ancestral maximum likelihood of evolutionary trees is hard
- 2004
-
Ingår i: Journal of Bioinformatics and Computational Biology. - 0219-7200 .- 1757-6334. ; 2:2, s. 257-271
-
Tidskriftsartikel (refereegranskat)abstract
- Maximum likelihood (ML) (Felsenstein, 1981) is an increasingly popular optimality criterion for selecting evolutionary trees. Finding optimal ML trees appears to be a very hard computational task - in particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years, no such hardness result has been obtained so far for ML. In this work we make a first step in this direction by proving that ancestral maximum likelihood (AML) is NP-complete. The input to this problem is a set of aligned sequences of equal length and the goal is to find a tree and an assignment of ancestral sequences for all of that tree's internal vertices such that the likelihood of generating both the ancestral and contemporary sequences is maximized. Our NP-hardness proof follows that for MP given in (Day, Johnson and Sankoff, 1986) in that we use the same reduction from VERTEX COVER; however, the proof of correctness for this reduction relative to AML is different and substantially more involved.
|
|
| 2. |
- Akkuratov, Evgeny E., et al.
(författare)
-
Neanderthal and Denisovan ancestry in Papuans : A functional study
- 2018
-
Ingår i: Journal of Bioinformatics and Computational Biology. - : Imperial College Press. - 0219-7200 .- 1757-6334. ; 16:2
-
Tidskriftsartikel (refereegranskat)abstract
- Sequencing of complete nuclear genomes of Neanderthal and Denisovan stimulated studies about their relationship with modern humans demonstrating, in particular, that DNA alleles from both Neanderthal and Denisovan genomes are present in genomes of modern humans. The Papuan genome is a unique object because it contains both Neanderthal and Denisovan alleles. Here, we have shown that the Papuan genomes contain different gene functional groups inherited from each of the ancient people. The Papuan genomes demonstrate a relative prevalence of Neanderthal alleles in genes responsible for the regulation of transcription and neurogenesis. The enrichment of specific functional groups with Denisovan alleles is less pronounced; these groups are responsible for bone and tissue remodeling. This analysis shows that introgression of alleles from Neanderthals and Denisovans to Papuans occurred independently and retention of these alleles may carry specific adaptive advantages.
|
|
| 3. |
- Ma, Zhanyu, 1982-, et al.
(författare)
-
A variational bayes beta mixture model for feature selection in DNA methylation studies
- 2013
-
Ingår i: Journal of Bioinformatics and Computational Biology. - 0219-7200 .- 1757-6334. ; 11:4, s. 1350005-
-
Tidskriftsartikel (refereegranskat)abstract
- An increasing number of studies are using beadarrays to measure DNA methylation on a genome-wide basis. The purpose is to identify novel biomarkers in a wide range of complex genetic diseases including cancer. A common difficulty encountered in these studies is distinguishing true biomarkers from false positives. While statistical methods aimed at improving the feature selection step have been developed for gene expression, relatively few methods have been adapted to DNA methylation data, which is naturally beta-distributed. Here we explore and propose an innovative application of a recently developed variational Bayesian beta-mixture model (VBBMM) to the feature selection problem in the context of DNA methylation data generated from a highly popular beadarray technology. We demonstrate that VBBMM offers significant improvements in inference and feature selection in this type of data compared to an Expectation-Maximization (EM) algorithm, at a significantly reduced computational cost. We further demonstrate the added value of VBBMM as a feature selection and prioritization step in the context of identifying prognostic markers in breast cancer. A variational Bayesian approach to feature selection of DNA methylation profiles should thus be of value to any study undergoing large-scale DNA methylation profiling in search of novel biomarkers.
|
|
