NAME: shrub (simulated history recombination upper bound) SYNOPSIS: shrub [-d #] [-l #] [-b #] [-n #] [-f] [-r] [-e] [-g name] datafile OPTIONS: (See README-SHRUB for a more detailed description of the program.) -d # Display setting. 0: Only display final results (Default). 1: Display the original and the reduced data. 2: Display as in 1 + display local bound matrices for global lower bounds. -l # Fast lower bound method to be used in branch and bound. 1: Hudson and Kaplan's bound. 2: Approximate haplotype bound using distinct columns and rows. (Default: 1) -b # Degree of branching. The maximum number of row removals to be tried, in fast upper bound computation, for every matrix in step 3' of the algorithm. (Default: 2) -n # Number of runs to be executed. (Default: 3) -f Turn off full branch and bound. -r Root known. The first sequence is assumed to be the root sequence. -e Suppress mutation labels on edges. -g name Output an ARG with the computed number of recombination events into a file. The output is in GML format. NOTE : 1) In general, choosing higher degree of branching leads to better fast upper bounds, but increases computation time. 2) If you are not using full branch and bound, the quality of bound generally depends on what options are used. We recommend trying out both "-l 1" and "-l 2" options. Depending on the data set, one may work much better than the other. Also, -b and and -n options should be explored as well. EXAMPLES : shrub datafile shrub -b 1 -n 50 datafile shrub -b 3 -n 1 datafile shrub -l 1 -n 3 datafile shrub -l 1 -f datafile shrub -g graphics.gml datafile shrub -l 1 -f -g graphics.gml datafile --------------------------------------------------------------------------- DATA FILE : The first line of the data file is ignored. If you like, you may put a description of the data there. The data should be in 0,1. (White space is allowed between columns.) Each sequence should be placed in its own row. EXAMPLE : An example data set (Kreitman.dat) is included. Try running "shrub -g Kreitman.gml Kreitman.dat" to check that everything works correctly. GRAPH VIEWING: The GML file generated by the program can be viewed using a software of your choice. We recommend VGJ (Visualizing Graphs with Java), which can be downloaded free of charge from the following webpage: http://www.eng.auburn.edu/department/cse/research/graph_drawing/graph_drawing.html NOTE: You need to place the three GIF files ("*-ball.gif") in the main VGJ directory. 1) Go to the main VGJ directory. (default: graph_drawing) 2) Start VGJ. (java EDU/auburn/VGJ/VGJ &) 3) Click on "Start a Graph Window" to bring up a viewing window. 4) On the menu bar, choose "File" and then "Open (GML)." 5) When you first open a GML file generated by SHRUB, everything looks clustered at a point. To expand the graph, choose "Algorithms" --> "Tree" --> "Tree Down" 6) Although step (4) makes the graph viewable, you might still wish to rearrange certain things. For example, some directed edges might point upward instead of downward. To rearrange the graph manually, click on "Select Nodes" under "Mouse Action," located to the left of the graph. Using the mouse, try rearranging the nodes to your liking. BUG REPORT : Please report bugs to Yun S. Song AUTHOR : Yun S. Song