A method for identification of highly conserved elements and evolutionary analysis of superphylum Alveolata

BMC Bioinformatics

Research Article

Oleg A. Zverkov¹  Vassily A. Lyubetsky¹  Lev I. Rubanov¹  Alexandr V. Seliverstov¹ 

[1] Institute for Information Transmission Problems (Kharkevich Institute), Russian Academy of Sciences, Bolshoi Karetnyi per. 19, Building 1, 127051, Moscow, Russia;

关键词: Phylogeny;    Ultraconserved element;    Highly conserved element;    Dense subgraph;    Apicomplexan parasites;    Alveolates;   

DOI  :  10.1186/s12859-016-1257-5

 received in 2016-05-05, accepted in 2016-09-13,  发布年份 2016

来源: Springer

【 摘 要 】

BackgroundPerfectly or highly conserved DNA elements were found in vertebrates, invertebrates, and plants by various methods. However, little is known about such elements in protists. The evolutionary distance between apicomplexans can be very high, in particular, due to the positive selection pressure on them. This complicates the identification of highly conserved elements in alveolates, which is overcome by the proposed algorithm.ResultsA novel algorithm is developed to identify highly conserved DNA elements. It is based on the identification of dense subgraphs in a specially built multipartite graph (whose parts correspond to genomes). Specifically, the algorithm does not rely on genome alignments, nor pre-identified perfectly conserved elements; instead, it performs a fast search for pairs of words (in different genomes) of maximum length with the difference below the specified edit distance. Such pair defines an edge whose weight equals the maximum (or total) length of words assigned to its ends. The graph composed of these edges is then compacted by merging some of its edges and vertices. The dense subgraphs are identified by a cellular automaton-like algorithm; each subgraph defines a cluster composed of similar inextensible words from different genomes. Almost all clusters are considered as predicted highly conserved elements. The algorithm is applied to the nuclear genomes of the superphylum Alveolata, and the corresponding phylogenetic tree is built and discussed.ConclusionWe proposed an algorithm for the identification of highly conserved elements. The multitude of identified elements was used to infer the phylogeny of Alveolata.

【 授权许可】

CC BY   
© The Author(s). 2016