Algorithms for reconstruction of chromosomal structures

详细信息    查看全文

• 作者：Vassily Lyubetsky ; Roman Gershgorin ; Alexander Seliverstov…
• 关键词：Chromosomal structure ; Rearrangement of chromosomal structure ; Ancestral chromosomal structure ; Distance between chromosomal structures ; Lowest weight transformation of one chromosome structure into another ; Exact linear algorithm calculating the distance and transformation ; Generation of a phylogenetic tree of chromosomal structures ; Exact reconstruction algorithm with cubic complexity
• 刊名：BMC Bioinformatics
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：17
• 期：1
• 全文大小：1,714 KB
• 参考文献：1.Gorbunov KY, Gershgorin RA, Lyubetsky VA. Rearrangement and inference of chromosome structures. Mol Biol (Mosk). 2015;49(3):327–38.CrossRef
  2.Ed K, Newman Alexandra M. Practical guidelines for solving difficult linear programs. Surveys in Operations Research and Management Science. 2013;18(1–2):1–17.
  3.Ed K, Newman Alexandra M. Practical guidelines for solving difficult mixed integer linear programs. Surveys in Operations Research and Management Science. 2013;18(1–2):18–32.
  4.Schrijver A. Theory of linear and integer programming. New York: Wiley; 1986.
  5.Gorbunov KYu, Lyubetsky VA. Exact linear algorithms for structure rearrangement. Problems of InformationTtransmission. 2015. in press.
  6.Gorbunov KYu., Lyubetsky VA. Exact linear algorithms for the shortest rearrangement of structures with different operation weights. Problems of InformationTtransmission. 2015. in press.
  7.Braga MDV, Willing E, Stoye J. Double cut and join with insertions and deletions. J Comput Biol. 2011;18(9):1167–84.PubMed CrossRef
  8.da Silva PH, Machado R, Dantas S, Braga MDV. DCJ-indel and DCJ-substitution distances with distinct operation costs. Algorithms Mol Biol. 2013;8:21.PubMed PubMedCentral CrossRef
  9.Compeau PEC. DCJ-indel sorting revisited. Algorithms Mol Biol. 2013;8:6.CrossRef
  10.Compeau PEC. A generalized cost model for DCJ-indel sorting. Lect Notes Comput Sci. 2014;8701:38–51.CrossRef
  11.Hilker R, Sickinger C, Pedersen C, Stoye J. UniMoG - a unifying framework for genomic distance calculation and sorting based on DCJ. Bioinformatics. 2012;28:2509–11.PubMed PubMedCentral CrossRef
  12.Rusin LY, Lyubetskaya EV, Gorbunov KY, Lyubetsky VA. Reconciliation of gene and species trees. BioMed Res Int (Current Advances in Molecular Phylogenetics). 2014;2014:Article ID 642089. doi:10.​1155/​2014/​642089 .
  13.Gorbunov KY, Laikova ON, Rodionov DA, Gelfand MS, Lyubetsky VA. Evolution of regulatory motifs of bacterial transcription factors. In Silico Biol. 2010;10:0012.
  14.Lopatovskaya KV, Gorbunov KY, Rusin LY, Seliverstov AV, Lyubetsky VA. The evolution of proline synthesis transcriptional regulation in gammaproteobacteria. Mosc Univ Biol Sci Bull. 2010;65(4):211–2. doi:10.​3103/​S009639251004025​5 .CrossRef
  15.Alon N, Chor B, Pardi F, Rapoport A. Approximate maximum parsimony and ancestral maximum likelihood. IEEE/ACM Trans Comput Biol Bioinf. 2010;7:183–7.CrossRef
  16.Blanchette M, Kunisawa T, Sankoff D. Gene order breakpoint evidence in animal mitochondrial phylogeny. J Mol Evol. 1999;49(2):193–203.PubMed CrossRef
  17.Chauve C, El-Mabrouk N, Tannier E. Models and Algorithms for Genome Evolution. 19 volume, Computational Biology, Springer; 2013. doi: 10.​1007/​978-1-4471-5298-9 .
  18.Yancopoulos S, Attie O, Friedberg R. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005;21:3340–6.PubMed CrossRef
  19.Hannenhalli S, Pevzner PA. Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem). In FOCS IEEE Computer Society; 1995:581–592. doi: 10.​1109/​SFCS.​1995.​492588 .
  20.Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements. Algorithms in Bioinformatics, LNCS. 2006;4175:163–73.CrossRef
  21.Kou L, Markowsky G, Berman L. A fast algorithm for Steiner trees. Acta Inform. 1981;15:141–5.CrossRef
  22.Gershgorin RA, Gorbunov KY, Seliverstov AV, Lyubetsky VA. Evolution of Chromosome Structures, “Information Technology and Systems 2015” An IITP RAS Interdisciplinary Conference & School (ITaS’15), Sochi, Russia, Sep 7–11 2015. 2015. p. 105–20.
  23.Martinez FV, Feijão P, Braga MDV, Stoye J. On the family-free DCJ distance and similarity. Algorithms Mol Biol. 2015;10:13. doi:10.​1186/​s13015-015-0041-9 .PubMed PubMedCentral CrossRef
  24.Zelikovsky A. An 11/ 6-approximation algorithm for the network Steiner problem. Algorithmica. 1993;9:463–70.CrossRef
  25.Cheng X, Du D-Z, editors. Steiner Trees in Industry. Dordrecht: Kluwer Academic Publishers; 2001.
  26.Zverkov OA, Seliverstov AV, Lyubetsky VA. Plastid-encoded protein families specific for narrow taxonomic groups of algae and protozoa. Mol Biol. 2012;46(5):717–26. doi:10.​1134/​S002689331205012​3 .CrossRef
  27.Lyubetsky VA, Seliverstov AV, Zverkov OA. Elaboration of the homologous plastid-encoded protein families that separate paralogs in magnoliophytes. Mathematical Biology and Bioinformatics. 2013;8(1):225–33 (in Russian).CrossRef
  28.Lyubetsky VA, Seliverstov AV, Zverkov OA. Transcription regulation of plastid genes involved in sulfate transport in Viridiplantae. BioMed Res Int. 2013;2013:413450.PubMed PubMedCentral CrossRef
  29.Zverkov OA, Seliverstov AV, Lyubetsky VA. A database of plastid protein families from red algae and Apicomplexa and expression regulation of the moeB gene. BioMed Res Int. 2015;2015:510598.PubMed PubMedCentral CrossRef
  30.Wei L, Xin Y, Wang D, Jing X, Zhou Q, Su X, et al. Nannochloropsis plastid and mitochondrial phylogenomes reveal organelle diversification mechanism and intragenus phylotyping strategy in microalgae. BMC Genomics. 2013;14:534.PubMed PubMedCentral CrossRef
  31.Imanian B, Pombert JF, Keeling PJ. The complete plastid genomes of the two ‘dinotoms’ Durinskia baltica and Kryptoperidinium foliaceum. PLoS ONE. 2010;5(5):E10711.PubMed PubMedCentral CrossRef
  32.Ong HC, Wilhelm SW, Gobler CJ, Bullerjahn G, Jacobs MA, McKay J, et al. Analyses of the complete chloroplast genome sequences of two members of the Pelagophyceae: Aureococcus anophagefferens CCMP1984 and Aureoumbra lagunensis CCMP1507. J Phycol. 2010;46(3):602–15.CrossRef
  33.Cattolico RA, Jacobs MA, Zhou Y, Chang J, Duplessis M, Lybrand T, et al. Chloroplast genome sequencing analysis of Heterosigma akashiwo CCMP452 (West Atlantic) and NIES293 (West Pacific) strains. BMC Genomics. 2009;9:211.CrossRef
  34.Wang X, Shao Z, Fu W, Yao J, Hu Q, Duan D. Chloroplast genome of one brown seaweed, Saccharina japonica (Laminariales, Phaeophyta): its structural features and phylogenetic analyses with other photosynthetic plastids. Mar Genomics. 2013;10:1–9.PubMed CrossRef
  35.Le Corguille G, Pearson G, Valente M, Viegas C, Gschloessl B, Corre E, et al. Plastid genomes of two brown algae, Ectocarpus siliculosus and Fucus vesiculosus: further insights on the evolution of red-algal derived plastids. BMC Evol Biol. 2009;9:253.PubMed PubMedCentral CrossRef
  36.Janouškovec J, Horak A, Obornik M, Lukes J, Keeling PJ. A common red algal origin of the apicomplexan, dinoflagellate, and heterokont plastids. Proc Natl Acad Sci U S A. 2010;107(24):10949–54.PubMed PubMedCentral CrossRef
  37.Janouškovec J, Liu SL, Martone PT, Carre W, Leblanc C, Collen J, et al. Evolution of red algal plastid genomes: ancient architectures, introns, horizontal gene transfer, and taxonomic utility of plastid markers. PLoS ONE. 2013;8(3):E59001.PubMed PubMedCentral CrossRef
  38.Sadovskaya TA, Seliverstov AV. Analysis of the 5′-leader regions of several plastid genes in protozoa of the phylum apicomplexa and red algae. Mol Biol. 2009;43(4):552–6. doi:10.​1134/​S002689330904003​7 .CrossRef
  39.Baurain D, Brinkmann H, Petersen J, Rodriguez-Ezpeleta N, Stechmann A, Demoulin V, et al. Phylogenomic evidence for separate acquisition of plastids in cryptophytes, haptophytes, and stramenopiles. Mol Biol Evol. 2010;27(7):1698–709.PubMed CrossRef
  40.Garg A, Stein A, Zhao W, Dwivedi A, Frutos R, Cornillot E, et al. Sequence and annotation of the apicoplast genome of the human pathogen babesia microti. PLoS ONE. 2014;9(10):e107939.PubMed PubMedCentral CrossRef
  41.Andreica A, Chira C. Best-order crossover in an evolutionary approach to multi-mode resource-constrained project scheduling. International Journal of Computer Information System and Industrial Management Applications. 2014;6:364–72.
  42.Andreica A, Chira C. Best-order crossover for permutation-based evolutionary algorithms. Appl Intell. 2014;42(4):751–76. doi:10.​1007/​s10489-014-0623-0 .CrossRef
  
• 作者单位：Vassily Lyubetsky (1)
  Roman Gershgorin (1)
  Alexander Seliverstov (1)
  Konstantin Gorbunov (1)
  
  1. Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Bolshoi Karetnyi lane, 19, 127051, Moscow, Russia
  
• 刊物主题：Bioinformatics; Microarrays; Computational Biology/Bioinformatics; Computer Appl. in Life Sciences; Combinatorial Libraries; Algorithms;
• 出版者：BioMed Central
• ISSN：1471-2105

文摘

Background One of the main aims of phylogenomics is the reconstruction of objects defined in the leaves along the whole phylogenetic tree to minimize the specified functional, which may also include the phylogenetic tree generation. Such objects can include nucleotide and amino acid sequences, chromosomal structures, etc. The structures can have any set of linear and circular chromosomes, variable gene composition and include any number of paralogs, as well as any weights of individual evolutionary operations to transform a chromosome structure. Many heuristic algorithms were proposed for this purpose, but there are just a few exact algorithms with low (linear, cubic or similar) polynomial computational complexity among them to our knowledge. The algorithms naturally start from the calculation of both the distance between two structures and the shortest sequence of operations transforming one structure into another. Such calculation per se is an NP-hard problem.