gsc-weighting (empty) → 0.1

raw patch · 4 files changed

+98/−0 lines, 4 filesdep +basedep +hierarchical-clusteringsetup-changed

Dependencies added: base, hierarchical-clustering

Files

• Data/Weighting/GSC.hs +37/−0
• LICENSE +30/−0
• Setup.hs +2/−0
• gsc-weighting.cabal +29/−0

@@ -0,0 +1,37 @@+module Data.Weighting.GSC where++import Data.List (foldl')+import Data.Clustering.Hierarchical (Dendrogram(..))++-- | /O(n^2)/ Calculates the Gerstein\/Sonnhammer\/Chothia+-- weights for all elements of a dendrogram.  Weights are+-- annotated to the leafs of the dendrogram while distances in+-- branches are kept unchanged.+--+-- Distances @d@ in branches should be non-increasing and between+-- @0@ (in the leafs) and @1@.  The final weights are normalized+-- to average to @1@ (i.e. sum to the number of sequences, the+-- same they would sum if all weights were @1@).+gsc :: Fractional d => Dendrogram d a -> Dendrogram d (a, d)+gsc (Leaf x) = Leaf (x,1)+gsc dendro   = let (wsum, nsum, r) = go wfinal undefined [] dendro+                   wfinal = (wsum / fromIntegral nsum)+               in r+    where+      position (Leaf _)       = 0 -- no difference from itself+      position (Branch d _ _) = d++      go wfinal _ cs (Branch d l r) =+          let (wl, nl, l') = go wfinal d ((el / wl) : cs) l+              (wr, nr, r') = go wfinal d ((er / wr) : cs) r++              el = d - position l -- edge length to left branch+              er = d - position r --          ...to right branch++              wsum = wl + wr + el + er+              nsum = nl + nr+          in wsum `seq` nsum `seq` (wsum, nsum, Branch d l' r')+      go wfinal d cs (Leaf x) =+          -- O(n) worst case, O(log n) best case (balanced dendrogram)+          let w = foldl' (\curw c -> curw + curw * c) d (tail cs)+          in (0, 1 :: Int, Leaf (x, w / wfinal))

@@ -0,0 +1,30 @@+Copyright (c)2010, Felipe Lessa++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Felipe Lessa nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,29 @@+Name:                gsc-weighting+Version:             0.1+Synopsis:            Generic implementation of Gerstein/Sonnhammer/Chothia weighting.+License:             BSD3+License-file:        LICENSE+Author:              Felipe Almeida Lessa+Maintainer:          felipe.lessa@gmail.com+Category:            Clustering+Build-type:          Simple+Cabal-version:       >= 1.6+Description:+  In their 1994 paper \"Volume Changes in Protein Evolution\",+  Gerstein, Sonnhammer and Chothia developed a weighting+  procedure for protein sequences to avoid over-represented+  sequences in the appendix \"A Method to Weight Protein+  Sequences to Correct for Unequal Representation\".  Although+  their method was developed for protein sequences, it is readily+  extended to work on any measurable set.+  .+  This package calculates GSC weights for any reasonable+  dendrogram.  If you want to recreate their algorithm, then just+  use @UPGMA@ as linkage and residue identity as distance+  function when creating the dendrogram.++Library+  Exposed-modules:+    Data.Weighting.GSC+  Build-depends: base == 4.*, hierarchical-clustering == 0.*+  GHC-options: -Wall