bp_bin/classify_taxonomy

   1 #!/usr/bin/env ruby
   2
   3 # Copyright (C) 2007-2012 Martin A. Hansen.
   4
   5 # This program is free software; you can redistribute it and/or
   6 # modify it under the terms of the GNU General Public License
   7 # as published by the Free Software Foundation; either version 2
   8 # of the License, or (at your option) any later version.
   9
  10 # This program is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 # GNU General Public License for more details.
  14
  15 # You should have received a copy of the GNU General Public License
  16 # along with this program; if not, write to the Free Software
  17 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18
  19 # http://www.gnu.org/copyleft/gpl.html
  20
  21 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  22
  23 # This program is part of the Biopieces framework (www.biopieces.org).
  24
  25 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> DESCRIPTION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  26
  27 # Classify records with taxonomy information.
  28
  29 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  30
  31 require 'pp'
  32 require 'maasha/biopieces'
  33
  34 # Class containing methods to construct a taxonomic tree recursively
  35 # for the classification of organisms. Currently only works with GreenGenes type of entries
  36 class TaxNode
  37   attr_accessor :level, :name, :count, :score, :children
  38
  39   # Method to initalize a TaxNode object.
  40   def initialize(level, name, count, score)
  41     @level    = level   # Taxonomic level e.g. phylum, class, etc
  42     @name     = name    # Name of organism
  43     @count    = count   # Number of times this organism was encountered
  44     @score    = score   # Similarity score
  45     @children = {}
  46   end
  47
  48   # Method to add to the taxonomic tree a GreenGenes entry.
  49   def add_gg(s_id, score, size)
  50     node = self
  51
  52     s_id.scan(/([\w])__([^;]+)/) do
  53       level = expand_level($1)
  54       name  = $2
  55
  56       if node.children[name].nil?
  57         node.children[name] = TaxNode.new(level, name, size * 1, size * score)
  58       else
  59         node.children[name].count += size * 1
  60         node.children[name].score += size * score
  61       end
  62
  63       node = node.children[name]
  64     end
  65   end
  66
  67   # Method to merge two TaxNodes.
  68   def merge(node_new, node_old = self)
  69     node_new.children.each do |name, child|
  70       if node_old.children[name]
  71         node_old.children[name].count += child.count
  72         node_old.children[name].score += child.score
  73
  74         merge(child, node_old.children[name])
  75       else
  76         node_old.children[name] = child
  77       end
  78     end
  79   end
  80
  81   # Method to flatten a taxonomic tree turning this into a list by recursive depth first traversal.
  82   def flatten(node = self, list = [])
  83     list << TaxNode.new(node.level, node.name, node.count, node.score)
  84
  85     node.children.each_value do |child|
  86       flatten(child, list)
  87     end
  88
  89     list
  90   end
  91
  92   # Method to recursively remove branches in taxonomic tree where the child count is less than or
  93   # equal to a given minimum.
  94   def debranch(min_count = nil)
  95     node = self
  96
  97     node.children.each do |name, child|
  98       node.children.delete(name) if child.count <= min_count
  99     end
 100
 101     node.children.each_value do |child|
 102       child.debranch(min_count)
 103     end
 104   end
 105
 106   # Method to recursively trim a taxonomic tree so that it only contains an unbranched tree,
 107   # which gives the lowest common ancestor.
 108   def lowest_common_ancestor
 109     node = self
 110
 111     node.children = {} if node.children.size > 1
 112
 113     node.children.each_value do |child|
 114       child.lowest_common_ancestor
 115     end
 116   end
 117
 118   # Method for iterating over a taxonomic tree.
 119   def each
 120     self.flatten.each do |node|
 121       yield node
 122     end
 123
 124     self
 125   end
 126
 127   # Method to convert a TaxNode to a Biopiece record.
 128   def to_bp
 129     record = {}
 130     record[:REC_TYPE] = "Classification"
 131     record[:LEVEL]    = @level
 132     record[:NAME]     = @name
 133     record[:COUNT]    = @count
 134     record[:SCORE]    = @count == 0 ? 0.0 : (@score / @count).round(2)
 135
 136     record
 137   end
 138
 139   private
 140
 141   # Method containing a helper hash to expand the phylogenetic level name.
 142   def expand_level(level)
 143     hash = {
 144       'd' => "domain",
 145       'k' => "kingdom",
 146       'p' => "phylum",
 147       'c' => "class",
 148       'o' => "order",
 149       'f' => "family",
 150       'g' => "genus",
 151       's' => "species"
 152     }
 153
 154     raise "unknown level: #{level}" unless hash[level]
 155
 156     hash[level]
 157   end
 158 end
 159
 160 casts = []
 161 casts << {:long=>'LCA',       :short=>'l', :type=>'flag', :mandatory=>false, :default=>nil, :allowed=>nil, :disallowed=>nil}
 162 casts << {:long=>'size',      :short=>'s', :type=>'flag', :mandatory=>false, :default=>nil, :allowed=>nil, :disallowed=>nil}
 163 casts << {:long=>'min_count', :short=>'m', :type=>'uint', :mandatory=>false, :default=>nil, :allowed=>nil, :disallowed=>nil}
 164
 165 options = Biopieces.options_parse(ARGV, casts)
 166
 167 tax_tree = TaxNode.new("root", "Root", 0, 0.0)
 168 tax_hash = {}
 169
 170 Biopieces.open(options[:stream_in], options[:stream_out]) do |input, output|
 171   input.each_record do |record|
 172     if record[:Q_ID] and record[:S_ID] and record[:SCORE]
 173       size = 1
 174
 175       if options[:size]
 176         if record[:Q_ID].match(/_(\d+)$/)
 177           size = $1.to_i
 178 #        else
 179 #          raise BiopiecesError, "Could not extract size from Q_ID: #{record[:Q_ID]}"
 180         end
 181       end
 182
 183       if options[:LCA]
 184         tax_hash[record[:Q_ID]] = TaxNode.new("root", "Root", 0, 0.0) unless tax_hash[record[:Q_ID]]
 185         tax_hash[record[:Q_ID]].add_gg(record[:S_ID], record[:SCORE].to_f, size)
 186       else
 187         tax_tree.add_gg(record[:S_ID], record[:SCORE].to_f, size)
 188       end
 189     else
 190       output.puts record
 191     end
 192   end
 193
 194   if options[:LCA]
 195     tax_hash.each_value do |tree|
 196       tree.debranch(options[:min_count]) if options[:min_count]
 197       tree.lowest_common_ancestor
 198     end
 199
 200     tax_hash.each_value do |tree|
 201       tax_tree.merge(tree)
 202     end
 203   end
 204
 205   tax_tree.each do |node|
 206     output.puts node.to_bp unless node.level == 'root'
 207   end
 208 end
 209
 210
 211 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 212
 213
 214 __END__