28 December 2016 in BMC Genomics
Amphipods (Crustacea) of Lake Baikal are a very numerous and diverse group of invertebrates generally believed to have originated by adaptive radiation. The evolutionary history and phylogenetic relationships in Baikalian amphipods still remain poorly understood. Sequencing of mitochondrial genomes is a relatively feasible way for obtaining a set of gene sequences suitable for robust phylogenetic inferences. The architecture of mitochondrial genomes also may provide additional information on the mechanisms of evolution of amphipods in Lake Baikal. Three complete and four nearly complete mitochondrial genomes of Baikalian amphipods were obtained by high-throughput sequencing using the Illumina platform. A phylogenetic inference based on the nucleotide sequences of all mitochondrial protein coding genes revealed the Baikalian species to be a monophyletic group relative to the nearest non-Baikalian species with a completely sequenced mitochondrial genome - Gammarus duebeni. The phylogeny of Baikalian amphipods also suggests that the shallow-water species Eulimnogammarus has likely evolved from a deep-water ancestor, however many other species have to be added to the analysis to test this hypothesis. The gene order in all mitochondrial genomes of studied Baikalian amphipods differs from the pancrustacean ground pattern. Mitochondrial genomes of four species possess 23 tRNA genes, and in three genomes the extra tRNA gene copies have likely undergone remolding. Widely varying lengths of putative control regions and other intergenic spacers are typical for the mitochondrial genomes of Baikalian amphipods. The mitochondrial genomes of Baikalian amphipods display varying organization suggesting an intense rearrangement process during their evolution. Comparison of complete mitochondrial genomes is a potent approach for studying the amphipod evolution in Lake Baikal.
21 December 2020 in Optimization Methods and Software
Over the last two decades, the PageRank problem has received increased interest from the academic community as an efficient tool to estimate web-page importance in information retrieval. Despite numerous developments, the design of efficient optimization algorithms for the PageRank problem is still a challenge. This paper proposes three new algorithms with a linear time complexity for solving the problem over a bounded-degree graph. The idea behind them is to set up the PageRank as a convex minimization problem over a unit simplex, and then solve it using iterative methods with small iteration complexity. Our theoretical results are supported by an extensive empirical justification using real-world and simulated data.
5 August 2015 in Journal of Global Optimization
11 September 2018 in Optimization Methods and Software
In the late sixties, N. Shor and B. Polyak independently proposed optimal first-order methods for solving non-smooth convex optimization problems. In 1982 A. Nemirovski proposed optimal first-order methods for solving smooth convex optimization problems, which utilized auxiliary line search. In 1985 A. Nemirovski and Yu. Nesterov proposed a parametric family of optimal first-order methods for solving convex optimization problems with intermediate smoothness. In 2013 Yu. Nesterov proposed a universal gradient method which combined all good properties of the previous methods, except the possibility of using auxiliary line search. One can typically observe that in practice auxiliary line search improves performance for many tasks. In this paper, we propose the apparently first such method of non-smooth convex optimization allowing the use of the line search procedure. Moreover, it is based on the universal gradient method, which does not require any a priori information about the actual degree of smoothness of the problem. Numerical experiments demonstrate that the proposed method is, in some cases, considerably faster than Nesterov's universal gradient method.