Chromosome structures: reduction of certain problems with unequal gene content and gene paralogs to integer linear programming

BMC Bioinformatics

Research Article

Roman Gershgorin¹  Konstantin Gorbunov¹  Vassily Lyubetsky² 

[1] Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Bolshoy Karetny per. 19, build.1, 127051, Moscow, Russia;Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Bolshoy Karetny per. 19, build.1, 127051, Moscow, Russia;Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Leninskiye Gory 1, Main Building, 119991, Moscow, Russia;

关键词: Chromosome structure;    Chromosomal rearrangement;    Ancestral genome;    Evolution along the tree;    Reconstruction of ancestral genomes;    Transformation of chromosome structures;    Parsimony principle;    Integer linear programming;    Efficient algorithms;   

DOI  :  10.1186/s12859-017-1944-x

 received in 2017-03-19, accepted in 2017-11-15,  发布年份 2017

来源: Springer

【 摘 要 】

BackgroundChromosome structure is a very limited model of the genome including the information about its chromosomes such as their linear or circular organization, the order of genes on them, and the DNA strand encoding a gene. Gene lengths, nucleotide composition, and intergenic regions are ignored. Although highly incomplete, such structure can be used in many cases, e.g., to reconstruct phylogeny and evolutionary events, to identify gene synteny, regulatory elements and promoters (considering highly conserved elements), etc. Three problems are considered; all assume unequal gene content and the presence of gene paralogs. The distance problem is to determine the minimum number of operations required to transform one chromosome structure into another and the corresponding transformation itself including the identification of paralogs in two structures. We use the DCJ model which is one of the most studied combinatorial rearrangement models. Double-, sesqui-, and single-operations as well as deletion and insertion of a chromosome region are considered in the model; the single ones comprise cut and join. In the reconstruction problem, a phylogenetic tree with chromosome structures in the leaves is given. It is necessary to assign the structures to inner nodes of the tree to minimize the sum of distances between terminal structures of each edge and to identify the mutual paralogs in a fairly large set of structures. A linear algorithm is known for the distance problem without paralogs, while the presence of paralogs makes it NP-hard. If paralogs are allowed but the insertion and deletion operations are missing (and special constraints are imposed), the reduction of the distance problem to integer linear programming is known. Apparently, the reconstruction problem is NP-hard even in the absence of paralogs. The problem of contigs is to find the optimal arrangements for each given set of contigs, which also includes the mutual identification of paralogs.ResultsWe proved that these problems can be reduced to integer linear programming formulations, which allows an algorithm to redefine the problems to implement a very special case of the integer linear programming tool. The results were tested on synthetic and biological samples.ConclusionsThree well-known problems were reduced to a very special case of integer linear programming, which is a new method of their solutions. Integer linear programming is clearly among the main computational methods and, as generally accepted, is fast on average; in particular, computation systems specifically targeted at it are available. The challenges are to reduce the size of the corresponding integer linear programming formulations and to incorporate a more detailed biological concept in our model of the reconstruction.

【 授权许可】

CC BY   
© The Author(s). 2017

【 图 表 】

12864_2015_1944_Article_IEq13.gif

12864_2017_3920_Article_IEq6.gif

12864_2016_2388_Article_IEq4.gif

12864_2017_3920_Article_IEq5.gif

12864_2017_3920_Article_IEq4.gif

12864_2016_2580_Article_IEq3.gif

12864_2016_2793_Article_IEq40.gif

12864_2017_3605_Article_IEq3.gif

12864_2017_3492_Article_IEq1.gif

12864_2015_2055_Article_IEq34.gif

12864_2016_2793_Article_IEq36.gif

12864_2015_2055_Article_IEq32.gif

12864_2016_3353_Article_IEq41.gif

12864_2015_2296_Article_IEq52.gif

12864_2016_2897_Article_IEq12.gif

12864_2017_3733_Article_IEq29.gif

12864_2016_3098_Article_IEq6.gif

12864_2015_2192_Article_IEq21.gif

12864_2017_3670_Article_IEq9.gif

12888_2016_877_Article_IEq17.gif

12864_2017_3990_Article_IEq4.gif

12864_2017_3771_Article_IEq6.gif

12888_2016_877_Article_IEq14.gif

12864_2017_3487_Article_IEq17.gif

12864_2017_4116_Article_IEq3.gif

12864_2017_3487_Article_IEq16.gif

12864_2016_2871_Article_IEq10.gif

12864_2017_3733_Article_IEq17.gif

12870_2017_1059_Article_IEq7.gif

12864_2015_2192_Article_IEq11.gif

12864_2017_4196_Article_IEq2.gif

12864_2017_3669_Article_IEq5.gif

12888_2016_877_Article_IEq4.gif

12864_2017_3669_Article_IEq4.gif

12906_2017_1593_Article_IEq25.gif

12864_2016_3105_Article_IEq10.gif

12906_2015_Article_682_TeX2GIF_IEq2.gif

12864_2016_3353_Article_IEq8.gif

12906_2017_1593_Article_IEq16.gif

12864_2017_4186_Article_IEq1.gif

12864_2016_3440_Article_IEq46.gif

12864_2017_3938_Article_IEq12.gif

12864_2015_2300_Article_IEq4.gif

12864_2017_4318_Article_IEq1.gif

12864_2017_3938_Article_IEq8.gif

12864_2017_3938_Article_IEq6.gif

12864_2017_4191_Article_IEq2.gif

12864_2017_4191_Article_IEq1.gif

12864_2017_3938_Article_IEq3.gif

12864_2017_3496_Article_IEq2.gif

12864_2017_3938_Article_IEq1.gif

12864_2017_3500_Article_IEq20.gif