lib/Text/Tradition/Stemma.pm

   1 package Text::Tradition::Stemma;
   2
   3 use Bio::Phylo::IO;
   4 use Encode qw( decode_utf8 );
   5 use File::chdir;
   6 use File::Temp;
   7 use File::Which;
   8 use Graph;
   9 use Graph::Reader::Dot;
  10 use IPC::Run qw/ run binary /;
  11 use Text::Tradition::StemmaUtil qw/ phylip_pars_input /;
  12 use Moose;
  13
  14 has collation => (
  15     is => 'ro',
  16     isa => 'Text::Tradition::Collation',
  17     required => 1,
  18     weak_ref => 1,
  19     );
  20
  21 has graph => (
  22     is => 'rw',
  23     isa => 'Graph',
  24     predicate => 'has_graph',
  25     );
  26
  27 has distance_trees => (
  28     is => 'ro',
  29     isa => 'ArrayRef[Graph]',
  30     writer => '_save_distance_trees',
  31     predicate => 'has_distance_trees',
  32     );
  33
  34 has distance_program => (
  35         is => 'rw',
  36         isa => 'Str',
  37         default => '',
  38         );
  39
  40 sub BUILD {
  41     my( $self, $args ) = @_;
  42     # If we have been handed a dotfile, initialize it into a graph.
  43     if( exists $args->{'dot'} ) {
  44         $self->graph_from_dot( $args->{'dot'} );
  45     }
  46 }
  47
  48 sub graph_from_dot {
  49         my( $self, $dotfh ) = @_;
  50         # Assume utf-8
  51         binmode( $dotfh, ':utf8' );
  52         my $reader = Graph::Reader::Dot->new();
  53         my $graph = $reader->read_graph( $dotfh );
  54         if( $graph ) {
  55                 $self->graph( $graph );
  56                 # Go through the nodes and set any non-hypothetical node to extant.
  57                 foreach my $v ( $self->graph->vertices ) {
  58                         $self->graph->set_vertex_attribute( $v, 'class', 'extant' )
  59                                 unless $self->graph->has_vertex_attribute( $v, 'class' );
  60                 }
  61         } else {
  62                 warn "Failed to parse dot in $dotfh";
  63         }
  64 }
  65
  66 sub as_dot {
  67     my( $self, $opts ) = @_;
  68
  69     # Get default and specified options
  70     my %graphopts = ();
  71     my %nodeopts = (
  72                 'fontsize' => 11,
  73                 'hshape' => 'plaintext',        # Shape for the hypothetical nodes
  74                 'htext' => '*',
  75                 'style' => 'filled',
  76                 'fillcolor' => 'white',
  77                 'shape' => 'ellipse',   # Shape for the extant nodes
  78         );
  79         my %edgeopts = (
  80                 'arrowhead' => 'open',
  81         );
  82         @graphopts{ keys %{$opts->{'graph'}} } = values %{$opts->{'graph'}}
  83                 if $opts->{'graph'};
  84         @nodeopts{ keys %{$opts->{'node'}} } = values %{$opts->{'node'}}
  85                 if $opts->{'node'};
  86         @edgeopts{ keys %{$opts->{'edge'}} } = values %{$opts->{'edge'}}
  87                 if $opts->{'edge'};
  88
  89         my @dotlines;
  90         push( @dotlines, 'digraph stemma {' );
  91         ## Print out the global attributes
  92         push( @dotlines, _make_dotline( 'graph', %graphopts ) ) if keys %graphopts;
  93         push( @dotlines, _make_dotline( 'edge', %edgeopts ) ) if keys %edgeopts;
  94         ## Delete our special attributes from the node set before continuing
  95         my $hshape = delete $nodeopts{'hshape'};
  96         my $htext = delete $nodeopts{'htext'};
  97         push( @dotlines, _make_dotline( 'node', %nodeopts ) ) if keys %nodeopts;
  98
  99         # Add each of the nodes.
 100     foreach my $n ( $self->graph->vertices ) {
 101         if( $self->graph->get_vertex_attribute( $n, 'class' ) eq 'hypothetical' ) {
 102                 # Apply our display settings for hypothetical nodes.
 103                 push( @dotlines, _make_dotline( $n, 'shape' => $hshape, 'label' => $htext ) );
 104         } else {
 105                 # Use the default display settings.
 106             push( @dotlines, "  $n;" );
 107         }
 108     }
 109     # Add each of our edges.
 110     foreach my $e ( $self->graph->edges ) {
 111         my( $from, $to ) = @$e;
 112         push( @dotlines, "  $from -> $to;" );
 113     }
 114     push( @dotlines, '}' );
 115
 116     return join( "\n", @dotlines );
 117 }
 118
 119
 120 # Another version of dot output meant for graph editing, thus
 121 # much simpler.
 122 sub editable {
 123         my $self = shift;
 124         my @dotlines;
 125         push( @dotlines, 'digraph stemma {' );
 126         my @real; # A cheap sort
 127     foreach my $n ( sort $self->graph->vertices ) {
 128         my $c = $self->graph->get_vertex_attribute( $n, 'class' );
 129         $c = 'extant' unless $c;
 130         if( $c eq 'extant' ) {
 131                 push( @real, $n );
 132         } else {
 133                         push( @dotlines, _make_dotline( $n, 'class' => $c ) );
 134                 }
 135     }
 136         # Now do the real ones
 137         foreach my $n ( @real ) {
 138                 push( @dotlines, _make_dotline( $n, 'class' => 'extant' ) );
 139         }
 140         foreach my $e ( sort _by_vertex $self->graph->edges ) {
 141                 my( $from, $to ) = @$e;
 142                 push( @dotlines, "  $from -> $to;" );
 143         }
 144     push( @dotlines, '}' );
 145     return join( "\n", @dotlines );
 146 }
 147
 148 sub _make_dotline {
 149         my( $obj, %attr ) = @_;
 150         my @pairs;
 151         foreach my $k ( keys %attr ) {
 152                 my $v = $attr{$k};
 153                 $v =~ s/\"/\\\"/g;
 154                 push( @pairs, "$k=\"$v\"" );
 155         }
 156         return sprintf( "  %s [ %s ];", $obj, join( ', ', @pairs ) );
 157 }
 158
 159 sub _by_vertex {
 160         return $a->[0].$a->[1] cmp $b->[0].$b->[1];
 161 }
 162
 163 # Render the stemma as SVG.
 164 sub as_svg {
 165     my( $self, $opts ) = @_;
 166     my $dot = $self->as_dot( $opts );
 167     my @cmd = qw/dot -Tsvg/;
 168     my( $svg, $err );
 169     my $dotfile = File::Temp->new();
 170     ## TODO REMOVE
 171     # $dotfile->unlink_on_destroy(0);
 172     binmode $dotfile, ':utf8';
 173     print $dotfile $dot;
 174     push( @cmd, $dotfile->filename );
 175     run( \@cmd, ">", binary(), \$svg );
 176     $svg = decode_utf8( $svg );
 177     return $svg;
 178 }
 179
 180 sub witnesses {
 181     my $self = shift;
 182     my @wits = grep { $self->graph->get_vertex_attribute( $_, 'class' ) eq 'extant' }
 183         $self->graph->vertices;
 184     return @wits;
 185 }
 186
 187 #### Methods for calculating phylogenetic trees ####
 188
 189 before 'distance_trees' => sub {
 190     my $self = shift;
 191     my %args = (
 192         'program' => 'phylip_pars',
 193         @_ );
 194     # TODO allow specification of method for calculating distance tree
 195     if( !$self->has_distance_trees
 196         || $args{'program'} ne $self->distance_program ) {
 197         # We need to make a tree before we can return it.
 198         my $dsub = 'run_' . $args{'program'};
 199         my( $ok, $result ) = $self->$dsub();
 200         if( $ok ) {
 201             # Save the resulting trees
 202             my $trees = _parse_newick( $result );
 203             $self->_save_distance_trees( $trees );
 204             $self->distance_program( $args{'program'} );
 205         } else {
 206             warn "Failed to calculate distance trees: $result";
 207         }
 208     }
 209 };
 210
 211 sub run_phylip_pars {
 212     my $self = shift;
 213
 214     # Set up a temporary directory for all the default Phylip files.
 215     my $phylip_dir = File::Temp->newdir();
 216     # $phylip_dir->unlink_on_destroy(0);
 217     # We need an infile, and we need a command input file.
 218     open( MATRIX, ">$phylip_dir/infile" ) or die "Could not write $phylip_dir/infile";
 219     print MATRIX phylip_pars_input( $self->collation->make_alignment_table() );
 220     close MATRIX;
 221
 222     open( CMD, ">$phylip_dir/cmdfile" ) or die "Could not write $phylip_dir/cmdfile";
 223     ## TODO any configuration parameters we want to set here
 224 #   U                 Search for best tree?  Yes
 225 #   S                        Search option?  More thorough search
 226 #   V              Number of trees to save?  100
 227 #   J     Randomize input order of species?  No. Use input order
 228 #   O                        Outgroup root?  No, use as outgroup species 1
 229 #   T              Use Threshold parsimony?  No, use ordinary parsimony
 230 #   W                       Sites weighted?  No
 231 #   M           Analyze multiple data sets?  No
 232 #   I            Input species interleaved?  Yes
 233 #   0   Terminal type (IBM PC, ANSI, none)?  ANSI
 234 #   1    Print out the data at start of run  No
 235 #   2  Print indications of progress of run  Yes
 236 #   3                        Print out tree  Yes
 237 #   4          Print out steps in each site  No
 238 #   5  Print character at all nodes of tree  No
 239 #   6       Write out trees onto tree file?  Yes
 240     print CMD "Y\n";
 241     close CMD;
 242
 243     # And then we run the program.
 244     my $program = File::Which::which( 'pars' );
 245     unless( -x $program ) {
 246                 return( undef, "Phylip pars not found in path" );
 247     }
 248
 249     {
 250         # We need to run it in our temporary directory where we have created
 251         # all the expected files.
 252         local $CWD = $phylip_dir;
 253         my @cmd = ( $program );
 254         run \@cmd, '<', 'cmdfile', '>', '/dev/null';
 255     }
 256     # Now our output should be in 'outfile' and our tree in 'outtree',
 257     # both in the temp directory.
 258
 259     my @outtree;
 260     if( -f "$phylip_dir/outtree" ) {
 261         open( TREE, "$phylip_dir/outtree" ) or die "Could not open outtree for read";
 262         @outtree = <TREE>;
 263         close TREE;
 264     }
 265     return( 1, join( '', @outtree ) ) if @outtree;
 266
 267     my @error;
 268     if( -f "$phylip_dir/outfile" ) {
 269         open( OUTPUT, "$phylip_dir/outfile" ) or die "Could not open output for read";
 270         @error = <OUTPUT>;
 271         close OUTPUT;
 272     } else {
 273         push( @error, "Neither outtree nor output file was produced!" );
 274     }
 275     return( undef, join( '', @error ) );
 276 }
 277
 278 sub _parse_newick {
 279     my $newick = shift;
 280     my @trees;
 281     # Parse the result into a tree
 282     my $forest = Bio::Phylo::IO->parse(
 283         -format => 'newick',
 284         -string => $newick,
 285         );
 286     # Turn the tree into a graph, starting with the root node
 287     foreach my $tree ( @{$forest->get_entities} ) {
 288         push( @trees, _graph_from_bio( $tree ) );
 289     }
 290     return \@trees;
 291 }
 292
 293 sub _graph_from_bio {
 294     my $tree = shift;
 295     my $graph = Graph->new( 'undirected' => 1 );
 296     # Give all the intermediate anonymous nodes a name.
 297     my $i = 0;
 298     foreach my $n ( @{$tree->get_entities} ) {
 299         next if $n->get_name;
 300         $n->set_name( $i++ );
 301     }
 302     my $root = $tree->get_root->get_name;
 303     $graph->add_vertex( $root );
 304     _add_tree_children( $graph, $root, $tree->get_root->get_children() );
 305     return $graph;
 306 }
 307
 308 sub _add_tree_children {
 309     my( $graph, $parent, $tree_children ) = @_;
 310     foreach my $c ( @$tree_children ) {
 311         my $child = $c->get_name;
 312         $graph->add_vertex( $child );
 313         $graph->add_path( $parent, $child );
 314         _add_tree_children( $graph, $child, $c->get_children() );
 315     }
 316 }
 317
 318 no Moose;
 319 __PACKAGE__->meta->make_immutable;
 320
 321 1;