"Daniel Sch?tz"  wrote in message
>
> caused by a project of "Jugend forscht" I want to know how I can
> reconstruct Wagner trees. Can someone tell me how to do? Or can > me
someone recommend a computer program that creates such
> trees?
>
Here's a link

http://www.faculty.virginia.edu/evolutionlabs/wagner_trees.html

since I'm a computer programmer implementing this looks mainly like donkey
work. Since you don't give your level of experience it is difficult to tell
you how to set about it.

The idea of Wagner tree is that we have a list of characters for each
organism (tail length, no toes, skin colour etc), each coded by a small
number of integer states. The states are arranged so that numbers ajacent
are most similar to each other - for number of toes the coding is obvious,
for tail length it could be length in inches, for skin colour you would have
to assign arbitrary numbers to grey, brown, and black.

We then calculate a hypothetical ancestor using the most primitive state of
all the traits.

To write a computer program you need to decide what sort of interface you
will have. The simplest thing to get the program up and running is to define
a text file format, where the user enters the character matrix and the
ancestor. However for a user-friendly program you would need to provide a
graphical interface.

You need to load your matrix. In C it will look like this

struct matrix
{
  int N; /* number of organisms */
  int n; /* number of traits */
  int **traits; /* 2d allocated trait matrix */
  int *ancestor; /* the ancestor */
};

The next thing you do is find the organism that is most similar to the
ancestor. This is pretty simple.

We then calculate the interval (difference) between the ancestor and the
nearest. This is the first interval on the tree.

Now we need to find the nearest to the interval. If ANC is the ancestor and
A is the nearest, the distance for B =

interval(ANC-B) + interval(A-B) - interval(ANC-A)

Once we have found the best match, we construct the common ancestor of A and
B (assume B is the best match). If ANC A and B have the same state then
obviously the hypothetical ancestor (HTU) has that state. If any two of ANC
A and B are the same then HTU takes that state. If ANC A and B are all
different then HTU is the average.

This should be quite easy to code.

Sometimes HTU ends up equal to A, which means that B is derived from A.
Otherwise, HTU is placed on the tree between ANC, A and B.

So we need some sort of structure to represent these intervals. Only binary
nodes are allowed.

typedef struct node
{
   node *ancestor;
   node *child1;
   node *child2;
   int *characters;
} NODE;

Keep a pointer to the root ancestor, and walk the tree recursively.

Now we have three intervals. We simply repeat the process until we have
added all organisms.
---
þ RIMEGate(tm)/RGXPost V1.14 at BBSWORLD * Info{at}bbsworld.com

---
 * RIMEGate(tm)V10.2áÿ* RelayNet(tm) NNTP Gateway * MoonDog BBS
 * RgateImp.MoonDog.BBS at 2/22/04 8:51:44 PM