Comparative genomics meets topology: a novel view on genome median and halving problems

BMC Bioinformatics

Research

Max A. Alekseyev¹  Pavel Avdeyev¹  Nikita Alexeev¹ 

[1] The George Washington University, Washington, DC, USA;

关键词: Median problem;    Halving problem;    Breakpoint graphs;    Embedded graphs;   

DOI  :  10.1186/s12859-016-1263-7

来源: Springer

【 摘 要 】

BackgroundGenome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of evolutionary events between them and genomes of the extant species. While these problems have been widely studied in past decades, their solutions are often either not efficient or not biologically adequate. These shortcomings have been recently addressed by restricting the problems solution space.ResultsWe show that the restricted variants of genome median and halving problems are, in fact, closely related. We demonstrate that these problems have a neat topological interpretation in terms of embedded graphs and polygon gluings. We illustrate how such interpretation can lead to solutions to these problems in particular cases.ConclusionsThis study provides an unexpected link between comparative genomics and topology, and demonstrates advantages of solving genome median and halving problems within the topological framework.

【 授权许可】

CC BY   
© The Author(s) 2016

【 图 表 】

Fig. 1

12864_2016_2889_Article_IEq3.gif

Fig. 1

Fig. 2

Fig. 2

Fig. 2

Fig. 1

12951_2017_270_Article_IEq10.gif

Fig. 8

Fig. 3

Fig. 3

Fig. 7

12951_2015_111_Article_IEq5.gif

Fig. 1

12951_2015_155_Article_IEq30.gif

Fig. 5

Fig. 6

12951_2017_270_Article_IEq9.gif

Fig. 2

12951_2017_270_Article_IEq8.gif

Fig. 1

12951_2015_111_Article_IEq4.gif

Fig. 1

13100_2023_302_Article_IEq7.gif

Fig. 2

Fig. 4

Fig. 5

12951_2015_155_Article_IEq28.gif

42004_2023_1020_Article_IEq18.gif

Fig. 3

Fig. 7

13100_2023_302_Article_IEq2.gif

13100_2023_302_Article_IEq1.gif

12951_2017_270_Article_IEq7.gif

42004_2023_1020_Article_IEq12.gif

Fig. 2

Fig. 7

Fig. 1

Fig. 3

12951_2015_111_Article_IEq2.gif

Fig. 1

Fig. 5

Fig. 6

12951_2015_155_Article_IEq27.gif

12951_2017_315_Article_IEq2.gif

12951_2015_155_Article_IEq26.gif

12951_2015_155_Article_IEq25.gif

12951_2015_155_Article_IEq24.gif

Fig. 2

12951_2017_270_Article_IEq5.gif

Fig. 3

Fig. 1

12951_2015_111_Article_IEq1.gif

Fig. 6

Fig. 4

Fig. 1

12951_2015_155_Article_IEq16.gif

Fig. 1

Fig. 9

12951_2015_155_Article_IEq7.gif

Fig. 4

Fig. 8

Fig. 4

Fig. 3

Fig. 2

Fig. 4

Fig. 1

Fig. 3

Fig. 1

40517_2023_273_Article_IEq9.gif

Fig. 2

40517_2023_273_Article_IEq6.gif

40517_2023_273_Article_IEq4.gif

Fig. 1

40517_2023_273_Article_IEq2.gif

Fig. 2

42004_2023_1025_Article_IEq7.gif

Fig. 9

Fig. 9

Fig. 4

Fig. 1

Fig. 4

Fig. 3

Fig. 4

41512_2023_158_Article_IEq26.gif

Fig. 2

Fig. 2

12951_2017_270_Article_IEq3.gif

Fig. 1

41512_2023_158_Article_IEq20.gif

Fig. 1

Fig. 8

Fig. 6

Fig. 2

Fig. 2

Fig. 6

Fig. 8

12951_2017_323_Article_IEq1.gif

Fig. 5

Fig. 3

41512_2023_158_Article_IEq2.gif

Fig. 7

41512_2023_158_Article_IEq1.gif

Fig. 1

Fig. 5

12936_2017_2051_Article_IEq86.gif

12936_2017_1932_Article_IEq15.gif

12936_2017_2051_Article_IEq85.gif

Fig. 1

Fig. 1

Fig. 7

Fig. 4

Fig. 3

Fig. 3

Fig. 6