Trees, Arrays, Networks and Optimization for Finding Patterns in Biological Sequences

author: Dan Gusfield, University of California

Description

a) The use of suffix trees and integer programming for finding optimal virus signatures. b) A current treatment of suffix-arrays and their uses. In the last several years simple linear-time algorithms for building suffix arrays have been developed making explicit suffix-trees mostly obsolete. c) Algorithms for finding signatures (patterns) of historical recombination and gene-conversion in SNP (binary) sequences. The techniques here relate to graph-theory.

Categories

Top: Computer Science: Machine Learning: Pattern Recognition

You might be experiencing some problems with Your Video player.

*Slides*
0:00	Erice - Structured Pattern Detection and Exploitation
0:59	Outline
1:22	Kmer frequency
3:19	Weird (non-obvious) Patterns?
6:21	String Barcoding
7:11	Motivation
8:25	Motivation
9:17	Similar Work
9:34	Problem Definition
10:53	Example
12:26	Problem Complexity
13:03	Implementation
14:47	Implementation
16:00	Implementation: Suffix Trees
17:59	Implementation: Suffix Trees
18:22	Implementation: Solving
19:46	Implementation: Example
23:05	Implementation: Example
24:27	Implementation: Extensions
25:33	Results: Summary
27:35	Results: Summary
28:35	Conclusion
29:15	Future Work
29:22	Recognizing Patterns of Historical Recombination
34:08	Sequence Recombination
37:05	Network with Recombination Deriving a Set of Sequences
41:57	The biological Problem
46:34	Two Approaches
50:56	The Perfect Phylogeny Model for binary sequences
52:14	The converse problem
52:19	When can a set of sequences be derived on a perfect phylogeny?
54:25	A richer model
55:45	Network with Recombination
56:30	Elements of a Phylogenetic Network (single crossover recombination)
57:56	A Phylogenetic Network
59:13	Which Phylogenetic Networks are meaningful?
59:29	Minimization is NP-hard
59:38	Recombination Cycles
61:19	Galled-Trees
61:32	A galled-tree generating the sequences generated by the prior network.
64:49	Picture
65:17	Sales pitch for Galled-Trees
66:32	Old (Aug. 2003) Results
67:53	New work
68:05	Blobbed-trees: generalizing galled-trees
70:00	Every network is a tree of blobs. How do the tree parts and the blobs relate?
70:29	Incompatible Sites
70:56	1 2 3 4 5
72:39	The connected components of G(M) are very informative
76:51	Simple Fact

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.