Computer Science 4762, Winter '05
Course Diary
Copyright 2005 by H.T. Wareham
All rights reserved
Week 1,
Week 2,
Week 3,
Week 4,
(Midterm Exam Notes),
Week 5,
Week 6,
Week 7,
Week 8,
Week 9,
Week 10,
Week 11,
(Final Exam Notes),
Week 12,
Week 13,
(end of diary)
Wednesday, January 12 (Lecture #1)
[Chapter 1, S&M; Class Notes]
- Overview of course; dates and conventions.
- Basic biological concepts (Chapter 1, S&M):
- Cell Theory, Organic Chemistry, and the origins of
modern biology.
- Proteins as the structural / metabolic components of
the cell.
- The quest for the molecular basis of heredity.
- The road to DNA structure.
- The Genetic Code.
- mRNA as the intermediate between DNA and proteins.
- The Central Dogma of Molecular Biology:
| DNA> | ---------> | RNA |
-------> | Protein |
| Transcription | |
Translation | |
- The hierarchy of biological information:
- 1D: Molecular sequences
- 3D: Molecular / multi-molecular complex structure,
distribution of molecules within cells.
- 4D: Behavior of regulatory / metabolic networks over time.
- Digital molecular biology and the rise of computational biology.
- Three types of problems:
- Storage
- Visualization
- Analysis
- In this course, focus on analysis problems.
- Three main types of analysis problems:
- Infer structure from partial information.
- Find occurences of known patterns in a given
structure (pattern matching).
- Derive common patterns in a given set of structures
(pattern detection).
- The role of evolutionary theory in computational biology.
- Evolution as descent with modification.
- As a first approximation, molecular sequence
mutations and indels occur at random in the
sequence.
- Once species diverge from a common ancestor,
mutations in sequences inherited from that
ancestor occur independently in the
descendent species.
- Mutations in non-functional regions do not
affect an organism and are almost always
passed on to descendents; mutations in
functional regions are almost always
deleterious, i.e., they kill the
organism, and are rarely passed on to
descendants => functional regions evolve
more slowly than non-functional regions.
- Two consequences:
- Similar structures tend to have similar functions =>
To infer function of new structure, assess
similarity to structures of known function!
(pattern matching)
- Conservation is indicative of function => To
find functionally important regions, look for
conserved regions! (pattern detection)
- Evolution is the reason we can assume similarity (and
hence the basic problem of looking for similarity
among structures) is meaningful in computational biology.
- The role of algorithm efficiency in computational biology.
- The main reason for applying computational techniques
to biological data is that they are now too large to
analyze by hand.
- Biological datasets of all types are already ludicrously
large and are getting larger by the day; efficient
algorithms are our only hope of being able to perform
the necessary analyses.
Wednesday, January 19 (Lecture #2)
[Chapters 1 and 5 and Sections 2.1-2.3, 6.4, and 7.1, Gusfield]
- String Comparison
- Basic terminology ((proper) (sub)string, prefix, suffix)
(pp. 3-4, Gusfield).
- Two basic types of problems:
- Pattern Matching: Given a pattern-string P and a
text-string T, find all occurrences of P in T.
- Pattern Detection: Given set of text strings
T, find the set P of all pattern strings p such
that p occurs at least once in each string t in
T.
In general, patterns are much shorter than texts.
- One further distinctions for pattern problems is
exact vs. approximate pattern matching, i.e.,
how do you interpret "occurrence" of a pattern in a text?
- Exact Pattern Matching
- Naive exact pattern matching algorithm
(Section 1.1, Gusfield)
- Runs in THETA(|P||T|) time.
- On failing a match, this algorithm only advances the
pattern-search forward by one position in a text; it
also ignores all information gathered during an
unsuccessful match, as well as what we know already
about the pattern and the text.
- Can derive faster algorithms by preprocessing the
pattern or the text;, indeed, such preprocessing
allows O(|P| + |T|) time algorithms!
- Pattern Preprocessing Algorithms.
- In general, can exploit two kinds of information about
partial matches (Section 1.1.1, Gusfield):
- Shift pattern forward to longest suffix of matched
pattern that is also a prefix of the pattern.
- Shift pattern forward to leftmost occurrence of
leading pattern character in matched portion.
- Consider how we might exploit the first kind of
information using finite-state automata.
- Pattern-NFA Derivation Algorithm
- Runs in O(|P|) time; however, applyingsuch an
automaton may require O(2^{|P|}|T|) time =>
need to determinize!
- Pattern-DFA Derivation Algorithm
- Runs in O(|Sigma||P|^3) time.
- Pattern-RR-DFA Derivation Algorithm
- Allows symbol re-reads in text.
- Remove |Sigma| term be collapsing set of |Sigma|
transitions leaving each state to two
transitions, "normal" and "failure".
- Runs in O(|P|^3) time; can be collapsed to
O(|P|) time.
- The Knuth-Morris-Pratt (KMP) algorithm (Section 2.3, Gusfield)
- This algorithm matches patterns against texts
from left to right and computes pattern-shifts
for unsuccessful matches using information
about the longest suffix of the match that
equals a prefix of the pattern (which is
the first type of information listed above).
- The algorithm is typically phrased in terms
of a "failure function" F(i) that specifies
the point in the pattern at which matching
resumes on encountering a pattern-text
mismatch. These failure values re derived from
the failure transitions in the DFA derived by
the second DFA algorithm given above.
- Preprocessing the pattern
requires O(|P|) time and running a pattern against
a text requires O(|T|) time; hence, the KMP
algorithm runs in O(|P| + |T|) time.
- The Boyer-Moore algorithm (Sections 2.1-2.2, Gusfield)
- This algorithm matches patterns against texts from right to
left and computes pattern-shifts for unsuccessful matches
as the maximum shifts suggested by the (extended)
bad character and strong good suffix rules (which are
essentially rules that exploit the two types of information
listed above).
- Preprocessing the pattern to exploit these rules
requires O(|P|) time and running a pattern against
a text requires O(|T|) time; hence, the Boyer-Moore
algorithm runs in O(|P| + |T|) time (the analysis
required to show this bound on running time is
non-trivial).
- Note that shifts relative to the bad character rule
are often large, especially for strings over large
alphabets, which means that in practice, the
algorithms behavior with respect to T is sub-linear.
- All told, the Boyer-Moore algorithm uses several
individually unassuming mechanisms that
interact in unexpected ways to give the best
expected running time of any known exact
pattern matching algorithm.
- Text Preprocessing Algorithms
- Keyword Trees
- A keyword tree is a compact encoding of a set
patterns in a tree whose edges are labelled
with symbols and whose nodes are labeled with
pattern identifiers.
- In a keyword tree, each stored pattern has
a corresponding unique path from the root
of the tree to some node v such that the
pattern is the concatenation of the labels on
the edges leading to v and the label of v is
the pattern's identifier.
- For a set P of z patterns, each of length at
most m, can construct the corresponding
keyword tree in O(zm) time.
- Keyword trees have the interesting property that the
set of all patterns stored in the tree that have a prefix
s is described by the set of pattern identifiers labeling
nodes in the subtree of the keyword tree rooted at the
node v reached from the root by following the edges
specified by s (subtree property).
- This property is not all that useful in
keyword trees; however, given the proper set of patterns,
it can be exploited to great effect.
- Suffix Trees (Chapter 5, Gusfield)
- One of the great under-appreciated data structures
in Computer Science.
- A suffix tree is essentially a keyword
tree built from the set of suffixes
(labelled in order from largest to
smallest) of a string T$ for a given
string T, where $ is a character not
occuring in T. Character $ ensures
that no suffix is a prefix of any other,
hence gauranteeing that only leaf-nodes
are labelled with suffix identifiers.
- Note that a suffix tree differs from a
keyword tree in that edges are
labelled with strings instead of
individual symbols and no vertex
except the root can have degree 2.
- Can create suffix tree in O(|T|^2) time
using the keyword tree algorithm
(any string T has |T| suffixes, each of
length at most |T|); however there are
a number of algorithms (McCreight,
Weiner, Ukkonen) for creating suffix
trees in O(|T|) time (sort of; see notes
on alphabet-independent algorithms
below).
- The subtree property guarantees that
the identifiers of all suffixes with
a particular prefix will be in the
subtree of the suffix tree rooted at
the node reachable via that prefix;
as each occurrence of a pattern in
a string corresponds to a suffix
of that string with the pattern as a
prefix, exact pattern matching can be
done using suffix trees in O(|P| + |T|)
time.
- Alphabet-independent vs. alphabet-dependent
algorithms (Gusfield, Section 6.5.1)
- The running times given above
for the Aho-Corasick and suffix tree
creation algorithms are true only if the
alphabet Sigma is fixed; as keyword and
suffix trees must store and search arrays
of edge labels relative to symbol-label
at each non-leaf tree node, general
versions of these algorithms must have
either an additional |Sigma| multiplicative
term in their space complexities or an
additional log |Sigma| multiplicative term in
their time complexities.
- No such adjustment is required for the
pattern-preprocessing algorithms examined
previously as such algorithms
only care about symbol matches and
mismatches and are hence alphabet-independent.
- Alphabet-independent algorithms are more
efficient; however, alphabet-dependent
algorithms seem to be more general-purpose and
more easily adaptable to solve other problems.
- Exact Pattern Detection
- Exact pattern detection is essentially the problem
of, given a set of strings S, finding the set P of
all strings that occur as substrings in S.
- The naive algorithm for the common substring
problem selects a string s from S and determines,
for each of the O(m^2) substrings of s, whether or
not that substring occurs in each of the remaining
strings in S. This algorithm runs in
O(zm^3) time ((O(m^2) substrings of s) x (z - 1
pattern matchings against the remaining strings in S)
x (O(m + m) = O(m) time for each such matching)).
- Can solve this problem using generalized suffix trees
(Section 6.4, Gusfield)
- A generalized suffix tree stores the suffixes
associated a set P of given patterns; to ensure
uniqueness of leaf-labeling, each pattern
p in P has its own unique terminator-symbol
and the leaves of the tree are labelled with
identifier-pairs of the form (x,y) where x
is the identifier of pattern p in P and y
is the identifier of the suffix in p.
- The subtree property guarantees that
the identifiers of all suffixes with
a particular prefix will be in the
subtree of the suffix tree rooted at
the node reachable via that prefix;
as each occurrence of T in a pattern p
corresponds to a prefix of some suffix of p,
exact substring matching can be done using
generalized suffix trees in O(zm + n) time,
where there are z patterns, each of length at
most m, in P and the length of T is n.
- If we construct the generalized suffix
tree for S and further annotate each internal node
in the tree with the number of distinct strings in S
that have suffixes in the subtree rooted at that
node, can solve this problem in O(zm) time!
((O(zm) time for generalized suffix tree
construction) + (O(zm) time for annotation tree
traversal) + (O(zm) time for common-substring
collection tree traversal)) (generalization of
algorithms given in Section 7.4, Gusfield).
- The subtree property, in conjunction with the
augmentation of internal tree nodes with various
statistics about the labels in the subtrees
rooted at those nodes, make suffix trees and
generalized suffix trees very useful data structures
for solving a number of problems in string
comparison (see Chapters 7 and 9, Gusfield).
- From what we've seen, exact pattern matching and detection
can be done very efficiently -- unfortunately, this will
rarely be the case once we allow approximate matching
of patterns.
Wednesday, January 26 (Lecture #3)
[Sections 11.1-11.6, Gusfield; Section 3.6.1, S&M; Class Notes]
- String Comparison (Cont'd)
- Approximate Pattern Matching
- Formalize notion of one string being similar to
(dissimilar to) another string by a similarity
(distance) matching function f() on pairs of strings and
a threshold k; that is, rephrase pattern matching problem as
looking for all substrings s in a given text
T such that f(s,P) >= k (f(s,P) <= k).
- Properties of matching functions.
- A distance function should satisfy the following
four axioms:
- For all x, d(x,x) = 0
- For all distinct x and y, d(x,y) > 0
- For all x and y, d(x,y) = d(y,x) (symmetry)
- For all x, y, and z, d(x,y) <= d(x,z) + d(z,y)
(the triangle inequality)
A distance function that satisfies all four axioms is called
a metric and a distance function that only satisfies
the first three is called a semi-metric.
- A similarity function need not satisfy any axioms.
- Compute function values relative to
sequences of basic operations (symbol matches,
symbol mismatches, and symbol insertion/deletions
(indels)) transforming one string into
the other (transcripts).
Requires an underlying (|Sigma| + 1) x
(|Sigma| + 1) scoring matrix c that
defines the similarity or distance
between any two characters in the extended
string-alphabet (string alphabet + the
special indel symbol).
- Derive matching function score from transcript by summing
the scores of all operations in the transcript
relative to M.
- Example Some commonly used matching functions.
- Distance
- Hamming (matches = 0, mismatches = 1;
requires strings to be of same length)
- Edit (matches = 0, mismatches = indels = 1)
- Weighted Edit (arbitrary distance scoring matrix)
- Similarity
- Longest Common Substring (matches = 1,
mismatches = indels = 0; matching region
must be a string in each given string)
- Longest Common Subsequence (matches = 1,
mismatches = indels = 0; matching region
must be a subsequence in each given
string)
- Similarity (arbitrary similarity scoring matrix)
- All this is fascinating stuff; however. how do
we actually compute approximate matches using
such functions? We will build a chain of
algorithms that start with general exact
pattern matching and end up with general
approximate pattern matching.
- Given pattern and text-strings p and
t on lengths m and n, respectively, each such
algorithm will create a (m + 1) x
(n + 1)-size table T, specify a
recurrence for filling in the values of
this table, and examine the values in the
final row of this filled-in table to
determine matches of p to
t.
- Exact Pattern Matching (Distance/Similarity)
- Approximate Pattern Matching
(Hamming Distance)
- Approximate Pattern Matching
(Weighted Symbol Distance/Similarity)
- Pairwise (Weighted) Edit Distance/Similarity
- Approximate Pattern Matching
((Weighted) Edit Similarity)
- Why approximate pattern matching is only
defined relative to weighted edit similarity.
Wednesday, February 2 (Lecture #4)
[Chapter 11 and Section 12.1, Gusfield; Sections 3.1-3.3, S&M]
- String Comparison (Cont'd)
- Approximate Pattern Matching (Cont'd)
- Pairwise Sequence Alignment
- Can also compute matching function values relative to
alignments
of the two strings to show matching regions.
- Alignments and transcripts are for our
purposes equivalent; that is, an alignment
graphically shows the results of applying
a transcript.
- Each transcript specifies one alignment; however,
each alignment may have many associated
transcripts.
- Derive matching function score from alignment by summing
the scores of all columns of the alignment
relative to M.
- Several options for match-extent of a given string
s relative to a given string s':
- Global alignment: Look for best alignment
of all of s with all of s'.
- Semi-global alignment: Look for best alignment
of s with s' that ignores various combinations
of initial and final indels.
- Local alignment: Look for the best alignment
of a region of s with a region of s'.
- Each type of alignment can be implemented with an
appropriate dynamic programming (DP) algorithm.
- Example: Recursive and DP algorithms
for computing Fibonacci numbers.
- DP algorithms essentially have four components:
- Interpretation of table-values D(i,j).
- Recurrence (recursive cases + base cases
(boundary conditions))
- DP table fill-in procedure.
- Traceback (optimal-value search region for
DP table + traceback finish point).
- The various types of alignment can be obtained
by minor changes to the recurrence and
traceback procedures of a basic template
algorithm.
- Example: The basic alignment template algorithm:
Longest Common Subsequence
(Section 11.6.2, Gusfield)
- Interpret D(i,j) as length of longest common subsequence
of prefix i of s and prefix j of s'.
- Recurrence is D(i,j) = MAX{D(i, j - 1),
D(i - 1,j), D(i - 1, j - 1) + C(i,j)}, where
C(i,j) = 1 if s(i) = s'(j) and 0 otherwise,
with boundary conditions
D(i,0) = D(0,j) = 0.
- Traceback starts at D(m,n) and goes back to D(0,0);
note that each traceback-path from D(m,n) to
D(0,0) corresponds to a longest common subsequence.
- Example: Global pairwise alignment (Section 11.3,
Gusfield; Section 3.2.1, S&M)
- Works for distance or similarity matching
functions.
- Interpret D(i,j) as best alignment between prefix i of
s and prefix j of s'.
- Recurrence is D(i,j) = OPT{D(i, j-1) + D(indel),
D(i - 1,j) + D(indel), D(i - 1, j - 1) +
M(s(i),s'(j)) with boundary conditions
D(i,0) = i * D(indel) and D(0,j) = j * D(indel),
where OPT is min or max depending on whether the
alignment is done relative to a distance or similarity
edit function and D(indel) is the cost of an indel
relative to any symbol in an alignment.
- Traceback starts at D(m,n) and goes back to D(0,0);
note that each traceback-path from D(m,n) to
D(0,0) corresponds to an optimal alignment.
- Example: Semi-global pairwise alignment (Sections 11.6.4-11.6.5, Gusfield;
Section 3.2.3, S&M).
- Works for similarity matching functions only.
- Interpret D(i,j) as with global alignment.
- Recurrence same as with global alignment.
- Boundary conditions and traceback vary depending
on what indels you want to ignore in which
sequence.
- Ignore initial indels in s (s'):
Initialize D(0,j) (D(i,0)) to 0.
- Ignore final indels in s (s'):
Traceback starts at optimal value in
last row (column) of matrix and goes
back to D(0,0).
- Can combine the 4 options above to create
2^4 - 1 = 15 possible forms of semi-global
alignment. Two of most popular are approximate
pattern matching (if pattern = s', ignore
initial and final indels in s') and end-space
free alignment(if aligning suffix of s with
prefix af s', ignore final indels in s and
ignore initial indels in s').
- Example: Local pairwise alignment (Section 11.7,
Gusfield; Section 3.2.2, S&M)
- Works for similarity matching functions only.
- Interpret D(i,j) as best alignment over all suffixes of
prefix i of s and all suffixes of prefix j of s'.
- Recurrent portion same as for global alignment with
inclusion of leading 0-term; boundary conditions
same as in semi-global alignment (D(i,0) =
D(0,j) = 0).
- Traceback starts at any maximum-value
cell in the table and continues back until a
0-value cell is reached.
- Change in recurrence allows start of optimal
alignment at any points in both strings and
traceback procedure allows termination of
region at any points in both strings.
- Linear space DP computation (Section 12.1, Gusfield;
Section 3.3.1, S&M)
- Follows from observation that during DP table
fill-in, only need values from two rows (or rather,
one row and one cell from the next row).
- Fairly trivial for computing cost of optimal
alignment; relies on divide-and-conquer procedure
to implement traceback in linear space, though.
- Gap cost schemes (Section 11.8, Gusfield; Sections
3.3.2-3.3.3, S&M)
- On occasion, want to further mold alignment to
minimize the number of gaps i.e., number
maximal strings of indels in both sequences.
- Several types of gap-cost schemes:
- Constant, e.g., score + WgG, where
Wg is the penalty for a gap and G is the
number of gaps.
- Affine, e.g., score + sum Wgs + GiWgc
where Wgs is the penalty for starting a
gap, Gi is the length in symbols of gap i, and Wgc
is the penalty for extending a gap by one symbol.
- Convex, e.g., score + sum Wgs + c(Gi)
where c is a convex function.
- Arbitrary, e.g., score + sum f(Gi),
where f is an arbitrary function.
- Computing distances or similarities relative to
convex or arbitrary gap costs effectively makes
the DP algorithm cubic rather than quadratic time;
however, it is possible to compute relative to
constant and affine gap costs in quadratic time.
Thursday, February 3
Midterm Exam Notes
I'm still making up your midterm exam but I have a pretty
good idea about what questions will be on it.
This test will be closed-book.
It will be 90 minutes long and has a total of 90 marks
(this is not coincidental; I have tried to make the number
of marks for a question equivalent to the number of minutes
it should take you to do it). The current layout is as
follows:
- Biological background / Pattern matching /
Pattern detection (50 marks)
- Pairwise sequence alignment (24 marks)
- Multiple sequence alignment (16 marks)
Things that will not be covered are details of the more
intricate algorithms we've looked at (Boyer-Moore, KMP) and
database search. You may find previous exams a good guide to
what I have in mind:
- In-Class Test #1 (Winter 2002) (8 pages:
PostScript /
PDF)
- In-Class Test #1 with answers (Winter 2002) (7 pages:
PostScript /
PDF)
- In-Class Test #1 (Winter 2003) (8 pages:
PostScript /
PDF)
- In-Class Test #1 with answers (Winter 2003) (7 pages:
PostScript /
PDF)
I hope the above helps, and I wish you all the best of luck
with this test.
Wednesday, February 9 (Lecture #5)
[Chapters 14 and 15, Gusfield; Sections 3.4-3.5, S&M; Class Notes]
- String Comparison (Cont'd)
- Approximate Pattern Detection
- Multiple sequence alignment
- A slightly different formulation of the general
recurrence for pairwise sequence alignment.
- Note that the indices in all subproblems
in pairwise alignment recurrences differ
by at most 1 from the indices in the
given problem.
- Reformulate recurrence as
D(a) = OPT {D(a - b) + M(c(b_1,s_1[a_1]),
c(b_2,s_2[a_2]))}
where a is the length-2 vector (a_1,a_2) of
the indices of D, b is a length-2 binary
(b_1,b_2) such that b_1 + b_2 > 0, the OPT
operator ranges over all valid b-vectors,
and
c(b_i,s_i[a_i]) is an indel if b_i is 0 and
s[a_i] if b_i is 1.
- Remember: Each choice made in assigning
a value to an entry of D corresponds to a
symbol-column in an alignment. Hence, we
are essentially scoring alignments in
an additive symbol-column-wise fashion
(this is not true of pairwise alignments
done under cost functions the handle
gaps (see end of last lecture)).
- General multiple sequence alignment.
- Focus for remainder of lecture on
additive symbol-column-wise schemes, i.e.,
no special gap-costs, over k > 2
sequences.
- Formulate recurrence as
D(a) = OPT {D(a - b) + f(a,b)}
where a is the length-k vector (a_1,a_2,...,a_k) of
the indices of D, b is a length-k binary
(b_1,b_2,...,b_k) such that \sum_{i} b_i >
0, the OPT operator ranges over all valid
b-vectors, and f() is a function that
assigns a cost to the symbol-column
specified by a and b.
- Time complexity of filling in such a
matrix is (# matrix cells) x (# b
vectors) x (time to evaluate f()) = n^k *
(2^k - 1) * T(f()) = O((2n)^kT(f())),
where n is the maximum length of the
given sequences.
- Time complexity of recovering an optimal
alignment is O(kn); time complexity of
recovering all optimal alignments may
be exponential!
- Space complexity of algorithm is O(n^k +
S(f())), where S(f()) is the space
complexity of computing f(). Even with
space-saving tricks, requires
O(n^{k - 1} + S(f())) space.
Hence, the space required and not the
running time is often the major
computational difficulty associated with
computing optimal multiple alignments.
- Most popular alignment functions constructed
from pairwise alignments among pairs of strings
from the given set.
- Phylogenetic multiple sequence alignment
- Given a (evolutionary) tree, label the
leaves of this tree with the given
sequences and assign sequences to the
internal nodes; the cost of the alignment is
then the sum of the pairwise alignments
along the tree edges.
- Has ideal biological justification; create
alignment that assume least amount of
evolutionary change relative to a given
tree,and hence may be most plausible in
an evolutionary sense.
- Can reconcile all pairwise alignments in a
single alignment using the "once an
indel, always an indel" policy. By
convention, upper k rows are given
sequences and lowermost rows are those
for internal vertices.
- Relative to general multiple sequence
alignment schema, f(a,b) is the optimal
cost of the 1-character string
phylogenetic alignment on the given
tree when the leaves are labelled
with c(b_i,s_i[a_i]), where
c(b_i,s_i[a_i]) is an indel if b_i is 0 and
s_i[a_i] if b_i is 1, and the internal
node character assignments range over all
such assignments. Oddly enough, this can
be computed in O(k) time (see lectures on
evolutionary trees later in the course).
- Sum-of-Pairs (SP) multiple sequence alignment
- The cost of an alignment is the sum of all
pairwise alignments between distinct
pairs of given strings.
- Has no biological justification; however,
does have nice mathematical properties.
- Relative to the general multiple sequence
alignment schema, f(a,b) = sum_{i = 1}^k
\sum_{j = i + 1}^k M(c(b_i,s_i[a_i]),
c(b_j,a)j[s_j]), where c() is defined above.
This requires O(k^2) time to compute.
- Contrary to many statements in the
literature, SP
alignment is more expensive
than phylogenetic alignment.
- SP does allow a nice heuristic that can
dramatically lower the number of matrix
cells that need to be considered.
Essentially, the pairwise alignments
induced by a sample (not necessarily
optimal) multiple alignment bound a
region around the main diagonal in the
matrix in which an optimal alignment
traceback path can exist (see Section
14.6.1 of Gusfield and Section 3.4.1 of
S&M for details).
- Star multiple sequence alignment
- Restriction of phylogenetic alignment
to have only one internal vertex.
- Phylogenetic, SP, and star alignment are all
NP-hard!
- NP-hardness of phylogenetic alignment
(Wang and Jiang (1994); Wareham (1995))
- NP-hardness of SP alignment
(Wang and Jiang (1994))
- NP-hardness of star alignment
(Sweedyk and Warnow (1995);
Cascuberta and de la Higuera (2000))
- Multiple sequence alignment heuristics
- Iterative pairwise alignment methods.
- Repeated-motif methods.
- Stochastic methods (Gibbs Sampling,
Hidden Markov Models (HMM)).
- Representations of patterns
- Pattern representations derived from alignments
- Profiles
- Consensus strings
- Alignment-independent pattern representations
- Center-sum strings
- General form: Find a string s and
substrings ss_1,ss_2,..,ss_k
of the given strings such that for
some approximate matching function
f(), \sum_{i = 1}^k (f(s,ss_i) is
optimized.
- Center-limit strings
- General form: Find a string s and
substrings ss_1,ss_2,..,ss_k
of the given strings such that for
some approximate matching function
f(), OPT_i f(s,ss_i) is
optimized.
- Both of these problems are NP-hard when
f() is Hamming or edit distance!
- NP-hardness of center-sum (Hamming)
(Li, Ma, and Wang (1999))
- NP-hardness of center-sum (Edit)
(Sweedyk and Warnow (1995);
Cascuberta and de la Higuera (2000))
- NP-hardness of center-limit (Hamming)
(Li, Ma, and Wang (1999))
- NP-hardness of center-limit (Edit)
(Cascuberta and de la Higuera (2000))
- Approximate patter detection, unlike exact
pattern detection, does not seem to have efficient
exact-solution algorithms. Hence, there are many
approximation algorithms and heuristics.
- Database Search Algorithms
- Why use sub-quadratic time string comparison
heuristics?
- Required to perform database search in
reasonable amount of time on large databases.
- Even if sufficient computing power is available
to do quadratic time string comparison in database
search in a reasonable amount of time,
heuristics are still useful as filters to
remove "obviously" bad database entries from
being considered with quadratic-time
exact algorithms.
- Classical algorithms
- FASTA
- BLAST
- Broadly speaking, FASTA locates promising
diagonals and derives matching regions, and
BLAST isolates promising regions and expands
along diagonals.
- Classical protein scoring matrices
Wednesday, February 16
Wednesday, February 23
- Midterm break; no lecture.
Wednesday, March 2 (Lecture #6)
[Chapter 17, Gusfield; Chapter 6, S&M;
Wareham (1993); Class Notes]
- Inferring Evolutionary Trees
- Background
- What is an evolutionary tree?
- An evolutionary tree for a set S of species is
a tree that represents a hypothesized series of
speciation events by which a common ancestral
species gave rise to the given set of species.
- The parts of such a tree have specific meanings:
- Leaves = given species
(observed taxonomic units (OTU))
- Edges = species lineages over time
- Internal nodes = speciation events /
ancestral species (hypothesized
taxonomic units (HTU))
- Such trees may be directed / rooted (in which
case the root node = the common ancestral
species of the given set of species) or
undirected / unrooted; the former explicitly
represents the direction of time, while the
latter preserves closeness of common ancestry.
- Weights may be associated with the edges
(branch lengths); these
weights correspond to actual evolutionary time
or some measure of mutation-distance (which may
may not be correlated with time if mutation
rates vary between lineages).
- Uses for evolutionary trees depend on the
time-depth of the given OTU:
- Species: Evolutionary biology / ecology,
e.g., adaptation vs ancestry in
salmon egg-laying strategies.
- Species + geographic locale: Biogeography,
e.g., biological proof of continental
drift.
- Populations: Population studies, e.g.,
Mitochondrial Eve.
- Individuals: Genealogical studies, e.g.,
The Case of the HIV Dentist.
- Types of data
- Distance matrix
- |S| x |S| matrix of pairwise distances
between species in |S|; satisfies some
combination of the distance axioms
discussed previously (see Lecture #3).
- d(i,j) = distance between OTU i and OTU j.
- Some new (and very useful) distance axioms:
4-Point Condition:
For all x, y, w, z in S, d(x,y) + d(w,z)
<= max(d(x,z) + d(w,y), d(x,w) + d(y,z))
- A distance matrix that is metric and
also satisfies this axiom is called
a tree metric (additive metric).
- This condition implies that the
distances in the given matrix are
additive evolutionary distances.
- A tree metric has a unique associated
additive tree.
Ultrametric condition:
For all x, y, z in S,
d(x,y) <= max(d(x,z) + d(y,z))
- A tree metric that also satisfies this
axiom is called an
ultrametric.
- This condition implies not only that
the given matrix distances are
evolutionary distances but moreover
that these distances are equivalent
to evolutionary time.
- An ultrametric has a unique associated
ultrametric tree (Theorem 17.1.2,
Gusfield).
- Distance data need not be tree metrics or
ultrametrics; however, courtesy of these
conditions, we at least know what
distance data must look like in order to
exactly fit some tree.
- Character matrix
- A character is some characteristic
shared by all species in S which takes
on different values (character
states) in different species,
e.g., flower color = {red, blue,
plaid}, stem length = {1, 4.5, 7.2, 9}.
- Character data is typically stored in a
matrix in which rows are OTU in S and
columns are characters.
- M(i,j) = Value of character j for OTU i.
- Characters differ in the number of
states (binary vs. multistate) and the
manners in which states may mutate
among themselves (unordered (all mutations
possible) vs. ordered (some mutations
forbidden)).
- Ideally, a character defines a
subtree-partition of an evolutionary tree
tree such that
the smallest possible number of mutations
is required to accommodate the character
within that tree (see "Character Matrix
Methods" in next lecture);
however, this may not be so.
- Types of problems
- Two broad approaches to inferring evolutionary
trees:
- Algorithm-based: Compute the tree for the
given data
relative to a particular algorithm.
- Criterion-based: Find the tree which yields
the best fit to the given data relative to
some (hopefully biologically motivated)
data/tree-fitting criterion.
- The majority of our time will be spent looking
at criterion-based methods.
- Problems relative to criterion-based methods
vary along two dimensions:
- Exact vs. approximate fit of data to tree.
- Fitting the data to a given tree
(given-tree) vs. finding the tree which
has the best fit to the data (find-tree).
- As the data exactly fits only one tree under
some of the
fitting criteria considered here, the above
yields three problems for those criteria --
namely, exact-fit tree, approximate-fit
given-tree, and approximate-fit find-tree.
- Methods used, regardless of type, should have
some biological justification; unfortunately,
as we shall see below, this has not always
been the case.
- Criterion-based approaches
- Distance Matrix Methods
- Exact-fit tree problems
- There are several popular low-order polynomial-time
algorithms for additive trees (Section 17.2.2,
Gusfield; Section 6.5.1, S&M); as ultrametrics
are a restricted form of tree metric, can
either use these algorithms or special faster
algorithms just for ultrametric trees
(Section 17.1.3, Gusfield; Section 6.5.2, S&M).
- Example: Deriving the additive tree
associated with a given tree metric using the
algorithm in Section 6.5.1 of S&M.
- Distance data is rarely additive and even more
rarely ultrametric; need to be able to fit
distance data to a tree approximately. How does one
do this, though?
- Each edge-weighted tree T has an associated
patristic matrix p such that p(i,j) =
sum of the edge-weights on the unique path in
T between OTU i and OTU j.
- Rephrase tree/data-fitting as the problem of
computing the similarity of (or distance
between) a distance matrix and a patristic
matrix!
- The most popular distance functions between
matrices are the F-statistics:
F_a(d,p) = \sum_{x,y in S} |d(x,y) - p(x,y)|^a
- F_2 = Least-squares fit criterion
(Cavalli-Sforza and Edwards (1967))
- Approximate-fit given-tree problems
- Can be done in polynomial-time using various
linear-algebra-based optimization techniques.
- Simple optimization may introduce negative
branch lengths; forces introduction of more
complex notions of fitting, e.g.,
dominant additive metrics / ultrametrics
(see Sections 2.1-2.2, Wareham (1993), and
references).
- Approximate-fit find-tree problems
- Exhaustive-enumeration methods unusable for |S| > 20 as
there are OMEGA(2^|S|) tree topologies with
|S| leaves, and this doesn't even start to
consider the various combinations of branch
lengths possible relative to a particular
topology.
- The find-tree problems relative to additive
and ultrametric trees for the most popular
F-statistics are NP-complete (see Section 2.2,
Wareham (1993), and references).
- Perhaps the problem is branch-lengths; what if we just
focus on inferring evolutionary tree topologies? Might
that make things easier? We will consider this in the
next lecture.
Wednesday, March 9 (Lecture #7)
[Chapter 17, Gusfield; Chapter 6, S&M; Felsenstein (1981, 1992);
Sankoff and Cedergren (1983); Swofford et al. (1996);
Wareham (1993); Class Notes]
- Inferring Evolutionary Trees (Cont'd)
- Criterion-based approaches (Cont'd)
- Character Matrix Methods
- Parsimony
- When does a character exactly fit an
evolutionary tree?
- This occurs when, for each state of
a character, the OTUs with that
character-state are all (and the
only) descendants of a particular
common-ancestor internal vertex
in the tree.
- A character with r states that
exactly fits a tree can be
accommodated by r - 1 mutations,
and these mutations occur on the
edges linking the internal-vertex
roots of the character-state
subtrees. It is in this sense
that a binary character specifies
an edge in its associated evolutionary
tree and an r-state character
specifies r - 1 edges.
- Each r-state character thus requires at least
r - 1 mutations to be accommodated on
an evolutionary tree.
- Note that while it is true that there is only
one tree that exactly fits a set of binary
characters, there may be many trees that
exactly fit a set of r-state characters.
Hence, need to consider all four types of
problems here, cf. distance matrix
methods in previous lecture.
- Exact-fit given-tree problems
- There are a variety of low-order
polynomial-time algorithms for this
problem when the given characters are
binary or the
number of characters is small (Sections
17.3.3-17.3.4, Gusfield; Sections 6.1-6.3,
S&M). For r-state characters, can apply
the low-order polynomial-time algorithm
that calls the given-tree algorithm for
Fitch parsimony described below to
determine a minimum (hopefully size r - 1)
set of mutations for each given character
relative to the given tree.
- Exact-fit find-tree problems
- The problem of determining whether there
is a tree that exactly fits all given
characters is also known as the
Perfect Phylogeny problem.
- There are a variety of low-order
polynomial-time algorithms for the
perfect phylogeny problem when the
given characters are binary or the
number of characters is small (Sections
17.3.3-17.3.4, Gusfield; Sections 6.1-6.3,
S&M), and there are even algorithms that
run in polynomial time for fixed r where
r is the maximum number of states in
any given character. However, the
Perfect Phylogeny problem is NP-complete
in general.
- Unfortunately, it is rare for a set of
characters to exactly fit a tree, as extra
mutations (homoplasy) may have been
introduced by various evolutionary processes
(convergence, lateral transfer) or
analytical errors (fusion of character
states, splitting of species).
- Two ways of approximately fitting
characters to trees:
- Maximum Compatibility
- Find the largest subset of the given
characters that exactly fit some
tree T (discard imperfect data).
- Minimum Evolution /
Maximum Parsimony
- Find the tree T that fits all of the
given characters such that sum of
the mutations required to fit the
characters to T is minimized
(accomodate imperfect data).
- The principle of maximum parsimony
states that, all things being equal,
the simplest solution is preferable;
hence, in an evolutionary sense,
the tree that requires the minimum
number of mutations to accommodate
the given data is the most
parsimonious.
- Note that assuming minimum evolution
to infer a tree is not the same as
assuming that evolution operates by
minimizing the number of mutations;
rather, it is a convenient
assumption for imposing some order
on trees based on how well they fit
the given data.
- There are different kinds of
maximum parsimony depending on
whether all mutations between
character states are possible
(Fitch parsimony) or certain types
of mutations are forbidden,
e.g., Camin-Sokal / Dollo
parsimony (see Section 2.1,
Wareham (1993), and references).
- Approximate-fit given-tree problems
- There are a variety of low-order
polynomial-time algorithms for determining
the minimum number of mutations required
to fit a character to a tree T relative
to various kinds of parsimony (Section
17.6.1, Gusfield; Swofford and Maddison
(1992); Swofford et al. (1996)).
- Approximate-fit find-tree problems
- Inferring trees for binary-character data
relative to both maximum compatibility and
Fitch
parsimony is NP-complete (see Section 2.2,
Wareham (1993), and references).
- Exact exponential-time algorithms may be
derived from algorithms for finding
cliques in graphs (maximum compatibility)
and Steiner trees in r-dimensional
implicit hypercubes (maximum parsimony).
- One can also modify various polynomial-time
approximation algorithms for finding
Steiner trees in graphs to give
polynomial-time approximation algorithms
for finding most parsimonious evolutionary
trees (Section 17.5.2, Gusfield;
Section 5.4, Wareham (1993)).
- It is very interesting to note that though the
perfect phylogeny and maximum compatibility
criteria neither have biological justifications
nor are widely-used by evolutionary
biologists, both have been the subject of
intensive research in the computational
biology community (as witnessed by the amount
of space devoted to these problems in our two
course textbooks). This is a product of both
the mathematical elegance of these criteria
relative to maximum parsimony and
various historical incidents. That being said,
this is a prime illustration of how
computational biology research can be misled
when it does not keep in touch with the
preferences and needs of practicing biologists.
- Note that Fitch parsimony can be viewed as
phylogenetic multiple sequence alignment
under Hamming instead of edit distance. This
means that various algorithms for inferring
most parsimonious trees can be readily adapted
to give algorithms for inferring phylogenetic
multiple sequence alignments (Section 17.6,
Gusfield; Sankoff and Cedergren (1983); see
also Wareham (1995)).
- Maximum Likelihood
- Ideally, one would like to build in statistical
models M of character evolution to infer those
trees T that have the greatest likelihood
P(D | T, M) of producing the given data D. Note
that relative to likelihood, there is no
distinction between exactly or approximately
fitting data to a tree -- we are simply
computing probabilities.
- Maximum-likelihood evolutionary tree inference
methods were first considered in the late
1960's (Cavalli-Sforza and Edwards (1967));
however, they were not considered useful at
that time because:
- known algorithms for computing likelihoods
even against given trees required
exponential time;
- there were no reliable character-evolution
models for morphological character data;
and
- even though there were adequate
character-evolution models for DNA
sequence data, there was not enough (or
indeed in many cases, any)
DNA sequence data available for species
of interest.
- Maximum likelihood has become a viable method
for inferring evolutionary trees through the
mitigation of the first and third of these
objections.
- Given-tree problems (topology + branch lengths)
- Standard formula requires evaluation of
all |\Sigma|^{n - 1} assignments of
symbols to the (n - 1) internal vertices
of a tree with n leaves, and hence
requires exponential time
(Felsenstein (1992)).
- Felsenstein (1981) developed a linear-time
algorithm that computes likelihoods for
internal vertices in a bottom-up (dynamic programming)
fashion (Felsenstein (1981, 1992)). This
algorithm is adapted from a similar
algorithm developed within mathematical
genetics for computing the likelihood
of a particular model of genetic
inheritance relative to a given pedigree.
- Given-tree problems (topology only) /
Find-tree problems
- Can be solved by various complex and
very computationally expensive numerical
optimization methods.
- Has recenty (2004) been shown to be
NP-hard!
- General methods for optimizing criteria over the space of
possible trees
- Exhaustive enumeration
- Branch-and-Bound
- Heuristics (Hill-climbing / Valley-descending)
- Given the NP-hardness of the find-tree versions
of the problems described above, these are
often the only practical algorithms; however,
their naive use can lead to problems when
interpreting the resulting trees, e.g.,
the rocky road to the Mitochondrial Eve
hypothesis.
- Algorithm-based approaches
- Distance matrix methods
- Neighbor joining
- Hierarchical clustering (see Lecture #9)
- Quartet-based methods
- Infer the trees for each 4-tuple of given
species and combine these trees in some way
to get the tree for all given species.
- Comparison of methods
- Ideally, criterion-based methods (and in particular
maximum parsimony and maximum likelihood) are
preferred over algorithm-based methods because
criterion-based methods are biologically justified and moreover
can also be used to rank trees relative to the data,
cf. algorithm-based methods that produce
a single tree for given data. However, the
computational difficulty of criterion-based methods
means that most biologists in practice use either
heuristics for these methods or algorithm-based
methods.
- Challenges:
- Develop faster algorithms for existing
criterion-based methods.
- Develop biologically palatable algorithm-based
methods.
Wednesday, March 16 (Lecture #8)
[Chapter 8, S&M; Reeke (1988); Samudrala (2000); Class Notes]
- Sequence Folding
- Background
- Function of RNA and protein complexes dependent
on folded 3-D structure.
- Relationship between sequence and structure is
not necessarily 1-1 -- radically different
sequences can fold to the same structure!
- Mechanism of structure
- RNA
- Base pairing (hydrogen bonds)
(canonical / Watson-Crick (A-U, G-C),
non-canonical)
- Base triples
- Protein
- Pairwise amino acid interactions,
e.g., cystine-cystine.
- Amino acid / environment interactions,
e.g., interactions with water
(hydrophobic/hydrophilic).
- Levels / Elements of structure
- Primary (sequence)
- Secondary (local folds)
- RNA (Helical, Hairpin loop, Bulge (either
sequence), interior loop (paired bulge),
pseudoknots (*))
- Protein (alpha-helix, beta-sheet
(parallel/anti-parallel), Loop / coil)
- Tertiary (global folds)
- Quaternary (multi-sequence folds)
- Folding process
- Requires proper environment, e.g.,
temperature, pH.
- Takes place in 1ms - 10s timescale.
- In many cases, seems to depend only on
primary sequence.
- Appears to fold first into secondary-structure
elements, which then assemble into global k
folds; this may be indicative of
folding-constraint "pipelines" (folding
funnels).
- Consistent fold to same structure; these
structures are hypothesized (but not proven)
to be those that that are global minima wrt
some free energy function.
- Levinthal's Paradox: Given the number of
possible configurations a sequence can adopt,
how does folding occur so quickly and
consistently?
- Two main types of problems:
- Sequence Folding: Given a sequence S,
what is the folded secondary / tertiary
structure of S?
- Sequence Design: Given a structure S,
what are the sequences that can fold to that
structure?
- Algorithms for sequence folding
- Several approaches:
- Direct (single sequence)
- X-ray crystallography
- Nuclear Magnetic Resonance (NMR)
- Comparative modeling (two sequences)
- Threading (sequence-model)
- Ab Initio Modeling (single sequence)
- Molecular dynamics
- Combinatorial optimization of fold
against a given energy function.
- Varies along three dimensions:
- Configuration space
(Euclidean vs. lattice)
- Level of structure
(secondary vs. tertiary)
- Level of element detail
(full vs. reduced)
- Direct approach manual-labor intensive and has some
interesting computational problems, e.g.,
reconstructing positions of elements from pairwise
element distances (distance geometry).
- Comparative approach interesting, but only works when
sequences are very similar and have very similar folds.
- In simplest cases, threading reduces to a somewhat more
complex form of pairwise alignment; however, if pairwise
interactions between elements is allowed in the model,
the problem becomes NP-hard!
Wednesday, March 23 (Lecture #9)
[Chapter 8, S&M; Draghici (2001); Reeke (1988); Samudrala (2000); Class Notes]
- Sequence Folding (Cont'd)
- Algorithms for Sequence Folding (Cont'd)
- Ab Initio Modeling
- Molecular dynamics is very basic algorithmically
(N-body interaction simulation); very interesting
from the viewpoint of parallel computing and
advanced hardware, though.
- Combinatorial optimization on structures is much
more interesting algorithmically.
- Secondary structure in RNA
- Independent base pairs (Section 8.1, S&M)
- Intuition
- Recurrence
- Note addition of base-case
D(i,i+1) = 0 to prevent base-pairing
between adjacent bases; this can be
extended to D(i,i + c) = 0 for some
c > 1 to prevent base-pairing between
bases that are within c bases of
each other.
- Algorithm: Both table fill-in and
traceback look an awful lot like
the corresponding algorithms for
matrix-chain parenthesization!
(Section 15.2, Cormen et al.
(2001))
- Runs in O(n^3) time and O(n^2) space.
- Example
- Dependent base pairs (Section 8.1, S&M)
- Have to modify basic algorithm to
allow embedded secondary structures,
e.g., helical / hairpin loop /
bulge / interior loop regions.
- Runs in O(n^4) time and O(n^2) space.
- Pseudoknots
- Can recognize very simple pseudoknots
(bent hairpin loop) in O(n^5) time
and O(n^2) space; however, general
determination of pseudoknots is
NP-hard (Lyngso and Pedersen (2000))
- There has also been some success in
deriving secondary structure via
variants of comparative modeling,
e.g., co-variation analysis.
Such approaches very good at picking out
non-canonical base pairs.
- Secondary structure in protein
- Can use variants of above; typically, use
stochastic pattern matching,
e.g., HMM.
- Tertiary structure in RNA / protein
- NP-hardness results
- Euclidean space
(Ngo and Marks (1992))
- 3D-lattice, full alphabet
(Unger and Moult (1993))
- 3D-lattice, reduced (HP) alphabet
(Crescenzi et al. (1998))
- 2D-lattice, reduced (HP) alphabet
(Berger and Leighton(1998),
Fraenkel (1993))
- Polynomial-time 11/8- (Hart and Istrail
(1996)) and 10/9- (Hart and Istrail (1997))
approximation algorithms for 3-D lattice
under reduced (HP) alphabet.
- All of this presupposes a brute-force type
search through the conformation space.
If there really are, as many believe,
kinetic constraints on folding, there
may be efficient algorithms that
exploit these constraints (not unlike the
way greedy and DP algorithms exploit
constraints on combinatorial
solution-spaces). Hence, NP-hardness may
not matter and Levinthal's Paradox may be an
illusion (Ngo, Marks, and Karplus (1994)).
- Given the current databases of sequences and
structures and the availability of computing power,
a new sequence is first analyzed computationally
against databases of sequences and structures;
ab initio modeling and direct methods are only
applied as a last resort (see pages 398-400,
Mount (2001)).
- Algorithms for sequence design
- Originally thought to be NP-hard for 2-D/3-D
lattices under a full alphabet (Hart (1997));
however, this paper has since been found to
have errors.
- Solvable in polynomial time for 2-D
(Piccolboni (1999)) and 3-D (Kleinberg (1999))
lattices under a reduced (HP) alphabet;
polynomial-time algorithms for 3-D lattices under
restricted kinds of full alphabets are given in
Kleinberg (1999).
- Restricted algorithms not useful in general but are
aids in exploring possible kinetic constraints on
folding (see Dill (1993) and references).
- Systems-Level Analyses
- Up until now in this course, our analyses have typically
focused on analyzing components of biological system
in isolation.
- Systems Biology: The inference and analysis of
biological systems.
- Genes and proteins create life in the manner in which the
gene and protein complements of an organism interact
over time; these interactions are described using
metabolic and gene-regulatory networks.
- If we want to understand and engineer life-processes,
we need special ways of inferring and studying these
networks:
- Microarrays: Assess network state (in terms of
activity level of DNA/ RNA and proteins) under
particular conditions.
- Networks: Predict network behavior under
particular conditions.
- Microarray analysis
- It is often useful to be able to detect DNA or
RNA strands with particular sequences or proteins
with particular 3-D shapes, e.g.,
diagnostics /assays => real-life pattern detection!
- Mechanisms of detection
- DNA/ RNA
- Double-strand hybridization
(sequence-specific)
- Gel electrophoresis (mass-specific)
- Protein
- Immunological reaction (shape-specific)
- Gel electrophoresis (mass-specific)
- Mass spectroscopy (mass-specific)
- Can do these detections one a sample-by-sample basis
using traditional methods; however, it is also
possible to do a large number of assays
simultaneously. Any situation in which one
runs a mixed sample against a set of assays
is called a microarray.
Monday, March 28
- Final Exam Notes
I'm making up the final exam.
This exam will be closed-book and has a total of 100 marks.
(this is not coincidental; I have tried to make the number
of marks for a question equivalent to the number of minutes
it should take you to do it). The current layout is as
follows:
- String-based Analyses (24 marks)
- Inferring Evolutionary Trees (22 marks)
- Sequence Folding / Microarray Analysis /
Network Analysis (20 marks)
- Algorith Design (24 marks)
Things that will not be covered are details of the more
intricate algorithms we've looked at.
All else is fair game -- this includes any algorithm
for which I did at least one example in class.
The questions on the assignments are guides to what I have in
mind, as are any questions from the midterm exam which
people did not do well (these are crying out to be asked
again). You may also find the following previous CS 4762
exams of help:
I hope the above helps, and I wish you all the best of luck
with this exam.
Wednesday, March 30 (Lecture #10)
[Draghici (2001); Class Notes]
- Microarray analysis (Cont'd)
- Types of microarray platforms
- DNA / RNA
- Double-strand hybridization against
miniaturized array of immobilized
single-stranded target sequences.
- Classified by type of surface on
which array is synthesized,
e.g., nylon membrane /
glass slide / silicon chip, and
synthesis method, e,g.,
traditional chemistry /
photolithography.
- Protein
- Immunological assays.
- Tandem mass spectroscopy (TMS) (**)
- Uses of microarray data:
- Diagnostics (known sequence)
- DNA sequencing-by-hybridization (SBH)
- Assess gene activity
- Assess protein activity
- Indirect (mRNA)
- Direct (protein)
- Can visualize a single microarray as giving
activity levels for a particular set of entities
relative to some sample; typically
perform a group of microarrays for
a set of related samples -- this yields an
entity (row) by sample (column) matrix.
- Use such matrices to do higher-level analysis by
grouping rows or columns by similarity
(clustering).
- Interpretation of clustering depends on the nature
of the samples in the data matrix.
- Samples are a set of organisms in
different states, e,g., a set of
healthy and diseased individuals.
- Group by sample / column: What are
the basic categories of individuals by
entity-activity patterns?
- Use to extract both finer classification of
samples and diagnostic markers for
categories in this classification.
- Samples are a set of organisms in
states corresponding to stages in a
particular process, e,g., a time-series
of organism development or a time-series of
organism response to disease (stages in
a type of cancer).
- Group by sample / column: What are
the basic stages occurring in the
time-series as defined by entity-activity
patterns?
- Group by entity / row: What are the
basic categories of stage-correlated
entities?
- Use to extract both basic stages of
system behavior and entities correlated
with (and possibly causing transitions
between) these stages.
- Types of clustering
- Let D be the set of objects being clustered and
D(i) be the ith object in D;
each object can be viewed as a vector of values
for a set of attributes.
- If samples (entities) are objects, entities
(samples) are attributes; hence, under
appropriate interpretations, can do
column-wise or row-wise clustering in a
microarray data matrix.
- Clustering of objects with respect to one or two
attributes easy to do visually using
histograms and scatterplots.
- Higher number of attributes require distance
functions d(x,y) between pairs of objects
x and y; use the
values of these pairwise distance functions
to define clusters of objects.
- Two main types of clustering methods:
- Partition clustering
- Partitions the set of objects such
that the objects inside each set in
the partition are more similar to
each other than to outsiders.
- Requires that the number K of sets in
the partition be given up front.
- Is NP-hard under many types of
distance functions (note
relationship to center-sum and
center-limit string
problems in pattern representation).
- Core heuristic algorithm:
for i = 1 to K do
let r_k be a randomly chosen point in D
while changes in clusters happen do
for i = 1 to K do
C_i = { x \in D | d(r_i,x) < d(r_j, x) for all j <> i}
for i = 1 to K do
r_i = the vector mean of the objects in C_i
- Provides good clusterings; however,
running
time and requirement that
number of clusters be specified
up front are problems, especially
with large poorly-characterized
datasets.
- Hierarchical clustering
- Impose a rooted tree on the set of
objects such that the level of
common ancestry between two objects
encodes their similarity.
- Create tree by successive splits of
larger sets (division) or fusions
of smaller sets (agglomeration)
- Requires measure of distance
d(C_i, C_j) between clusters
C_i and C_j.
- Core algorithm (agglomeration):
for i = 1 to |D| do
C_i = {D(i)}
while there is more than one cluster left do
for i = 1 to |D| do
for j = 1 to |D| do
compute and store d(C_i, C_j)
find clusters C_i and C_j with minimum d(C_i, C_j)
C_i = C_i U C_j
delete cluster C_j
- Runs in O(|D|^2T(d)) time, where T(d)
is the time required to compute the
pairwise cluster distance function.
- Has good running time and provides
useful clustering in
poorly-characterized datasets
without need to specify the number
of clusters up front;
however, requires manual (and
usually intuitive) intervention
to transform tree into usable
clusters.
Wednesday, April 6 (Lecture #11)
[Class Notes]
- Network analysis
- Microarray analysis typically derives descriptive
models of data, e.g., clusters; network analysis
concerned with predictive models.
- Network analysis
- All problems above have been defined relative to the
process of inferring and investigating a single genetic
network; however, there is also a need to compare
networks.
- Networks have arisen by evolution and thus have common
patterns in both structure and behavior. Hence, versions
of pattern matching and pattern detection problems
(phrased in terms of network structure or behavior) will
become increasingly useful as the set of known networks
grows, e.g., matching / detecting
metabolic and regulatory motifs.
References
Unless otherwise stated, all references above are to Gusfield (1997).
- Berger, B. and Leighton, T. (1998) "Protein folding in the
hydrophobic-hydrophilic (HP) model is NP-complete." In
Proceedings of the Second International Conference on
Computational Molecular Biology (RECOMB). ACM Press;
New York. 30-39.
- Cavalli-Sforza, L.L. and Edwards, A.W.F. (1967) "Phylogenetic
analysis: Models and estimation procedures." Evolution,
32, 550-570.
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2001)
Introduction to Algorithms (Second Edition). MIT Press;
Cambridge, MA.
- Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A.,
and Yannakakis, M. (1998) "On the complexity of protein folding."
Journal of Computational Biology, 5(3), 423-466..
- Dill, K.A. (1993) "Folding proteins: finding a needle in a
haystack." Current Opinion in Structural Biology,
3, 99-103.
- Draghici, S. (2001) "Tools for data analysis of
DNA microarray data." Tutorial notes, Sixth Pacific Symposium
on Biocomputing (PSB'2001). [Initial text portion given as class
handout]
- Edwards, A.W.F. (1996) "The origin and early development of the
method of minimum evolution for the reconstruction of
phylogenetic trees." Systematic Biology, 45(1), 79-91.
- Felsenstein, J.S. (1981) "Evolutionary trees from DNA sequences:
A maximum likelihood approach." Journal of Molecular
Evolution, 17, 368-376. [Given as class handout]
- Felsenstein, J.S. (1992) "Likelihood". Tutorial notes,
Workshop on Molecular Evolution; Marine Biological Laboratory,
Wood's Hole, MA. [Selected pages given as class handout]
- Gusfield, D. (1997) Algorithms on Strings, Trees, and Sequences:
Computer Science and Computational Biology. Cambridge
University Press, [Abbreviated above as Gusfield]
- Fraenkel, A.S. (1993) "Complexity of protein folding." Bulletin
of Mathematical Biology, 55(6), 1199-1210.
- Hart, W.E. (1997) "On the computational complexity of sequence
design problems." In Proceedings of the First ACM
International Conference on Computational Molecular Biology
(RECOMB). ACM Press; New York. 128-136.
- Hart, W.E., and Istrail, S.C. (1996) "Fast protein folding in the
hydrophobic-hydrophilic model within three-eighths of optimal."
Journal of Computational Biology, 3(1), 53-96.
- Hart, W.E., and Istrail, S.C. (1996) "Lattice and off-lattice side
chain models of protein folding: Linear time structure
prediction better than 86% of optimal." Journal of
Computational Biology, 4(3), 241-259.
- Kleinberg, J.M. (1999) "Efficient algorithms for protein sequence
design and the analysis of certain evolutionary fitness
landscapes." In Proceedings of the Third Annual
International Conference on Computational Molecular Biology
(RECOMB). ACM Press; New York. 226-237.
- Li, M., Ma, B., and Wang, L. (1999) "Finding Similar Regions in
Many Strings." In Proceedings of the 31st Annual ACM Symposium
on Theory of Computing (STOC). ACM Press; New York. 473-482.
- Lyngso, R.B. and Pedersen, C.N.S. (2000) "Pseudoknots in RNA
Secondary Structure." In Proceedings of the Fourth Annual
International Conference on Computational Molecular Biology
(RECOMB). ACM Press; New York. 201-209.
- Mount, D.W. (2001) Bioinformatics: Sequence and Genome
Analysis. Cold Spring Harbor Laboratory Press; Cold
Spring Harbor, NY. [Pages 398-400 given as class handout]
- Ngo, J.T. and Marks, J. (1992) "Computational complexity of a
problem in molecular structure prediction." Protein
Engineering, 5(4), 313-321.
- Ngo, J.T., Marks, J., and Karplus, M. (1994) "Computational
Complexity, Protein Structure Prediction, and the Levinthal
Paradox." In K. Merz and S. Le Grand (eds.) The Protein Folding
Problem and Tertiary Structure Prediction. Birkhauser;
Boston, MA. 433-506.
- Piccolboni, A. (1999) "On the complexity of the Canonical Method
for Sequence Design." Poster abstract, Third Annual International
Conference on Computational Molecular Biology (RECOMB).
- Reeke Jr., G.N. (1988) "Protein Folding: Computational Approaches
to an Exponential-Time Problem." Annual Review of Computer
Science, 3, 59-84.
- Samudrala, R. (2000) "Protein folding and protein structure
prediction." Tutorial notes, Fifth Pacific Symposium,
on Biocomputing (PSB'2000). [Initial text portion given as class
handout]
- Sankoff, D.S. and Cedergren, R.J. (1983) "Simultaneous comparison
of three or more sequences related by a tree." In D.S. Sankoff
and J.B. Kruskal (eds.) Time Warps, String Edits, and
Macromolecules: The Theory and Practice of Sequence
Comparison. Addison-Wesley; Reading, MA. 253-263.
[Given as class handout]
- Setubal, J. and Meidanis, J. (1997) Introduction to
Computational Molecular Biology. PWS Publishing Company.
[Abbreviated above as S&M]
- Sweedyk, Z. and Warnow, T. (1995) "The Tree Alignment Problem
is NP-Complete." Manuscript.
- Swofford, D.L. and Maddison, W.P. (1992) "Parsimony,
Character-State Reconstructions, and Evolutionary Inferences."
In R.L. Mayden (ed.) Systematics, Historical Ecology, and
North American Freshwater Fishes. Stanford University Press.
- Swofford, D.L, Olsen, G.J., Waddell, P.J., and Hillis, D.M. (1996)
"Phylogenetic Inference." In D.M. Hillis, C. Moritz, and
B.K. Mable (eds.) Molecular Systematics (Second Edition).
Sinauer Associates; Sunderland, MA. 407-514. [Pages 415-419 given
as class handout]
- Unger, R. and Moult, J. (1993) "Finding the lowest free-energy
conformation of a protein is NP-hard problem: Proof and
implications." Bulletin of Mathematical Biology,
55(6), 1183-1198.
- Wang, L. and Jiang, T. (1994) "On the complexity of multiple
sequence alignment." Journal of Computational Biology,
1(4), 337-348.
- Wareham, H.T. (1993) On the Computational Complexity of
Inferring Evolutionary Trees. M.Sc. thesis. Technical Report
no. 9301, Department of Computer Science, Memorial University of
Newfoundland, March 1993.
(
Abstract (text);
Document (PostScript/101 pages)
)
-
Wareham, H.T. (1995) "A Simplified Proof of the NP- and MAX
SNP-hardness of Multiple Sequence Tree Alignment."
Journal of Computational Biology, 2(4), 509-514.
(PostScript/7 pages)
Created: November 12, 2004
Last Modified: April 7, 2005