doc/bioinfo_jc/bioinfo-presentation.rst

   1 .. include:: <s5defs.txt>
   2
   3 =====
   4 Mussa
   5 =====
   6
   7 :Authors: Diane Trout
   8
   9 .. The contents of this directory contain the source
  10    for a presentation for the Caltech Bioinformatics Journal club.
  11
  12 .. footer:: Caltech Bioinformatics Journal Club
  13
  14 What is Mussa
  15 -------------
  16
  17 .. class:: small
  18
  19   Mussa is tool to search for conserved regions between several
  20   sequences. Hopefully regions detected as conserved will
  21   highlight potentially important DNA sequence features such as
  22   cis-regulatory modules, microRNA genes, and exons.
  23
  24   Mussa extends previous 2-way sequence comparison to N sequences.
  25
  26 Family Tree
  27 -----------
  28
  29 .. class:: small
  30
  31   Family Relations and Mussa started using the same sequence
  32   comparison algorithm but developed in different directions.
  33
  34     .. image:: familytree.png
  35         :alt: Gratutious software family tree
  36
  37   `Family Relations`_ focused on providing a robust usable piece
  38   of software.
  39
  40   Mussa focused on the N-way algorithm.
  41
  42   .. _`Family Relations`: http://cartwheel.caltech.edu/
  43
  44 Algorithm
  45 ---------
  46
  47 .. class:: small
  48
  49   To compute a result Mussa conceptually uses these modules
  50
  51     * Seqcomp
  52     * Test Transitivity
  53     * "Refinement"
  54
  55 Seqcomp
  56 -------
  57
  58 .. class:: small
  59
  60   The original seqcomp comparion uses a refinement of a fairly simple
  61   algorithm to compare two sequences.
  62
  63   Given window of size W and sequences S[0] and S[1]::
  64
  65      for x in range(len(S[0])-W):
  66        for y in range(len(S[1])-W):
  67          match = 0
  68          for i in range(W):
  69            if S[0][x+i] == S[1][y+i]:
  70              increment match
  71            if match > threshold:
  72              save indicies
  73
  74   The actual algorithm only needs to compare the base that
  75   "slid in" into window, and account for the base that "slid out"
  76
  77 Seqcomp
  78 -------
  79
  80 .. class:: small
  81
  82   Assume that in this case we need 3 matches out of 4
  83
  84     .. image:: 4bp_window_no_match.png
  85
  86   In this case there are none.
  87
  88 Seqcomp
  89 -------
  90
  91 .. class:: small
  92
  93    Assume that in this case we need 3 matches out of 4
  94
  95      .. image:: 4bp_window_match.png
  96
  97    However, now that we slid over one position there are now 4
  98    and so we would record 0, 5
  99
 100 Seqcomp
 101 -------
 102
 103 .. class:: small
 104
 105
 106   Once one pass is complete one of the sequences is reversed complimented
 107   and the process is repeated.
 108
 109   .. container:: incremental
 110
 111      When extending to more than two sequences, mussa needs to compare
 112
 113      (N * (N-1)) / 2 sequences
 114
 115 Test Transitivity
 116 -----------------
 117
 118 Refinement
 119 ----------
 120
 121 Limits
 122 ------
 123
 124   describe the difference between a long distance comparison
 125   and multiple closer comparisons. (should use some pictures for that)
 126
 127   paircomp/seqcomp
 128
 129   transitivity filter
 130
 131 How To Use
 132 ----------
 133
 134   Should this include pulling things from the tutorial?
 135   cover sucking things out of UCSC?
 136
 137