Diversity Graphs - Clustering Challenges in Biological Network - page 147

we have that

η ( v ) η ( v ) η ( v )= η ( v ) η ( v ) .

⊕ ⊕ ⊕

It follows that

g = η ( v )+ η ( v )= η ( v )+ η ( v ) ,

which is a contradiction.

Theorem 6.9. Assume that ( V , W , E ,η,γ ) is a diversity graph with η ( V )= H

G is a chain under and E as large as possible and that γ ( W )= .Thena

|G | minimum solution has cardinality +1 .

2 ,..., g |G | and let w 1 ,w 2 ,...,w |G | be

G as g

1 , g

Proof. List the elements of

such that γ ( w i )= g

i ,for i =1 , 2 ,...,

|G | G

.Wefirst construct a solution to

|G | γ ( w 1 )= g

1 . Then for

with cardinality +1. Choose v ∈V so that η ( v ) ≺

i

∈G there is a unique v i such that η ( v )+ η ( v i )= γ ( w i )= g

i .

every g ∈V

v,v 1 ,v 2 ,...,v |G | }

G and has cardinality |G | Then, η ( { ) solves +1.

|G |

We now show by induction on that there does not exists a solution with

|G | |G |

cardinality less than +1. This fact is clear if =1, and we assume the

claim is true when |G |≤ k . Assume that G is a chain of length k +1,andlet

V ) be a minimum solution. Let G = G \{ γ ( w k +1 )

η ( } , where we assume that

G are ordered so that the elements of

γ ( w 1 ) γ ( w 2 ) γ ( w k ) γ ( w k +1 ) . ≺ ≺ ... ≺ ≺

Since η ( V ) solves G and a minimum solution to G has cardinality |G | +1=

V ) k +1,wehavethat | η ( |≥ k +1. Suppose for sake of attaining a contradiction

|η ( V ) | = k +1. From the induction hypothesis η ( V ) is a minimum solution that

γ ( w k +1 ) for i =1 , 2 ,...,k , and from Lemma 6.4, this
leads to the contradiction that there is no v and v in

G .However, γ ( w i )

to ≺

V such that η ( v )+ η ( v )=

γ ( w k +1 ). Hence |V |≥ |G | k +2= +1. Since we have already demonstrated

|G | that a solution of size +1exists, the proof is complete.

Corollary 6.1 follows immediately from Theorem 6.9 and provides a bound on the
pure parsimony problem.

Corollary 6.1. Let ( V , W , E ,η,γ ) be a diversity graph such that η ( V )= H and

1 , 2 ,..., q ,whereeach γ ( i )

E is as large as possible. Partition W into W W W W

is a chain ordered by . Then a minimum solution has cardinality no greater than

|G |

+ q .