Advances in Bioinformatics and Computational Biology by Unknown

Author:Unknown
Language: eng
Format: epub
ISBN: 9783030464172
Publisher: Springer International Publishing

Fig. 3.Examples of block-interchanges impacting Weighted Cycle Graph structures. In (a) we show an outcome of applying a BI in four black edges. In (b) we show a BI applied in three black edges, and in (c) a BI is a applied in two black edges.

Proof

Christie [6] tells we can increase the number of cycles by at most 2. Two scenarios are possible: either (i) one cycle is split in three, or (ii) two cycles are split in four by a single block-interchange .

Let us consider the first scenario, and let C be the cycle split in three. If C is balanced, the best we expect is that creates three balanced cycles, so . Otherwise, at least one of the resulting cycles shall be unbalanced, since weights of black edges of the three cycles sum up to a value different from the sum of gray edge weights. Therefore, the best we expect is to create at most 2 balanced cycles, so again .

Let us consider the second scenario, and let C and D be the cycles split by the BI. C generates and , while D generates and . If C is balanced, and could be both balanced, but if C is unbalanced, only one of them can be balanced. Therefore the change is by at most 1. The same applies for D and the cycles generated by the BI ( and ). Therefore, a BI can use both C and D to generate at most 2 new balanced cycles, so .

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.