We may earn an affiliate commission when you visit our partners.
Pavel Pevzner
and
Michael Levin
The world and internet are full of textual information. We search for information using textual queries and read websites, books and e-mails.
Read more
The world and internet are full of textual information. We search for information using textual queries and read websites, books and e-mails.
Read more
The world and internet are full of textual information. We search for information using textual queries and read websites, books and e-mails.
These are all strings from a computer science point of view. To make sense of all this information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.
In this course, part of the Algorithms and Data Structures MicroMasters program, you will learn about:
- suffix trees;
- suffix arrays;
- how other brilliant algorithmic ideas help doctors to find differences between genomes;
- power lightning-fast Internet searches.
What you'll learn
- Key ideas for pattern matching and suffix trees
- Suffix arrays
- Burrows-Wheeler Transform for compression
- Applications of string algorithms in bioinformatics
Register for this course and see more details by visiting:
OpenCourser.com/course/x3d97j/string
Three deals to help you save
We found three deals and offers that may be relevant to this course.
Save money when you learn.
All coupon codes, vouchers, and discounts are applied automatically unless otherwise noted.
Use code at checkout.
Valid until December 4
Save on Select Programs
Stay ahead in a competitive job market and save with these programs.
Take
30%
off
EDXCYBER24
Valid for a limited time only
Future-proof your career
Access O'Reilly books, live events, courses, and more. Save with an annual subscription.
Take
15%
off
What's inside
Learning objectives
- Key ideas for pattern matching and suffix trees
- Suffix arrays
- Burrows-wheeler transform for compression
- Applications of string algorithms in bioinformatics
- Key ideas for pattern matching and suffix trees
- Suffix arrays
- Burrows-wheeler transform for compression
- Applications of string algorithms in bioinformatics
Syllabus
Weeks 1 and 2: Suffix Trees
How would you search for a longest repeat in a string in LINEAR time? In 1973, Peter Weiner came up with a surprising solution that was based on suffix trees, the key data structure in pattern matching. Computer scientists were so impressed with his algorithm that they called it the Algorithm of the Year. In this lesson, we will explore some key ideas for pattern matching that will - through a series of trials and errors - bring us to suffix trees.
Week 3 and 4: Burrows-Wheeler Transform and Suffix Arrays
Although EXACT pattern matching with suffix trees is fast, it is not clear how to use suffix trees for APPROXIMATE pattern matching. In 1994, Michael Burrows and David Wheeler invented an ingenious algorithm for text compression that is now known as Burrows-Wheeler Transform. They knew nothing about genomics, and they could not have imagined that 15 years later their algorithm will become the workhorse of biologists searching for genomic mutations. But what text compression has to do with pattern matching??? In this lesson you will learn that the fate of an algorithm is often hard to predict – its applications may appear in a field that has nothing to do with the original plan of its inventors.
Good to know
Good to know
Know what's good ,
what to watch for , and
possible dealbreakers
Examines string algorithms, which are essential for search engines and personalized medicine, making it highly relevant to tech and healthcare professionals
Taught by Michael Levin and Pavel Pevzner, renowned researchers in bioinformatics, increasing its credibility
Covers advanced topics like suffix trees and the Burrows-Wheeler Transform, appealing to learners with a strong foundation in computer science
Part of the Algorithms and Data Structures MicroMasters program, indicating its rigor and potential for career advancement
May require prerequisites or additional knowledge in computer science, which could pose a barrier for beginners
Save this course
Save String Processing and Pattern Matching Algorithms to your list so you can find it easily later:
Save
Save
Activities
Be better prepared
before
your course. Deepen your understanding
during
and
after
it. Supplement your coursework and achieve mastery of the topics covered
in String Processing and Pattern Matching Algorithms with these
activities:
Review the concept of longest common substring
Show steps
Refresh your understanding of longest common substring, a prerequisite for this course.
Browse courses on
String Algorithms
Show steps
-
Go through your notes or textbooks to recall the definition and properties of longest common substring
Organize your notes, assignments, and resources
Show steps
Enhance your learning experience by organizing your course materials effectively.
Show steps
-
Review your lecture notes, assignments, and any additional resources
-
Create a system for organizing these materials, such as folders or a digital notebook
Try out this interactive Pattern Matching Explorer
Show steps
Build a foundation with this interactive tool to visualize pattern matching and suffix trees.
Browse courses on
Pattern Matching
Show steps
-
Explore the 'Run Example' section to see the implementation of the algorithm
-
Go through the 'Try it Yourself' section to practice pattern matching with suffix trees
Ten other activities
Expand to see all activities and additional details
Show all 13 activities
Watch this video on 'Suffix Trees In 3 minutes'
Show steps
Reinforce your understanding with this concise visual explanation of suffix trees.
Browse courses on
Suffix Trees
Show steps
-
Watch the video in its entirety to grasp the fundamental concepts of suffix trees
Review basics of pattern matching
Show steps
Reinforce your knowledge of the basic concepts of pattern matching, which will help you better understand the advanced algorithms covered in the course.
Show steps
-
Read the textbook chapters on pattern matching.
-
Work through the practice problems at the end of the chapters.
Solve these practice problems on suffix trees
Show steps
Test your comprehension with a set of challenging practice problems on suffix trees.
Browse courses on
Suffix Trees
Show steps
-
Attempt to solve the problems on your own
-
Review the provided solutions to identify areas for improvement
Explore tutorials on Burrows-Wheeler Transform
Show steps
Familiarize yourself with the Burrows-Wheeler Transform and its applications, which will enhance your understanding of advanced string algorithms and their use in bioinformatics.
Browse courses on
Burrows-Wheeler Transform
Show steps
-
Find online tutorials or videos that explain the Burrows-Wheeler Transform.
-
Follow the tutorials, taking notes and working through the examples.
-
Implement a Burrows-Wheeler Transform algorithm in your preferred programming language.
Join a study group to discuss course concepts
Show steps
Engaging in discussions with peers will help you reinforce your understanding of the course concepts, identify areas where you need further clarification, and gain different perspectives.
Show steps
-
Find a study group or create one with classmates.
-
Meet regularly to discuss the course material, solve problems, and share insights.
-
Take turns leading the discussions and presenting your understanding of the concepts.
Create a diagram explaining the relationship between suffix trees and pattern matching
Show steps
Solidify your understanding by creating a visual representation of the connection between suffix trees and pattern matching.
Browse courses on
Suffix Trees
Show steps
-
Brainstorm the key components of suffix trees and pattern matching
-
Sketch out a diagram that illustrates how these components interact
-
Label the diagram with clear explanations
Solve coding challenges
Show steps
Practice applying the concepts of suffix trees to solve coding challenges, which will help you solidify your understanding and improve your problem-solving skills.
Browse courses on
Suffix Trees
Show steps
-
Find a set of coding challenges that focus on suffix trees.
-
Solve the challenges, working through the algorithms step by step.
-
Review your solutions and identify areas where you can improve your understanding.
Develop a visual representation of a suffix tree
Show steps
Creating a visual representation of a suffix tree will help you gain a deeper understanding of how suffix trees work and how they can be used to perform pattern matching.
Browse courses on
Suffix Trees
Show steps
-
Choose a suffix tree construction algorithm.
-
Implement the algorithm in your preferred programming language.
-
Use your implementation to construct a suffix tree for a given text.
-
Develop a visual representation of the suffix tree.
Build a program that implements a suffix tree for a given string
Show steps
Deepen your understanding by implementing a suffix tree from scratch.
Browse courses on
Suffix Trees
Show steps
-
Choose a programming language and familiarize yourself with its data structures
-
Design and implement the algorithm for constructing a suffix tree
-
Test your program with various input strings
Develop a software tool to visualize suffix tree constructions
Show steps
Creating a software tool will provide you with hands-on experience in applying the concepts of suffix trees and suffix arrays, deepening your understanding of their practical applications.
Browse courses on
Suffix Trees
Show steps
-
Design the functionality and user interface of your tool.
-
Choose a programming language and development environment.
-
Implement the core algorithms for suffix tree and/or suffix array construction.
-
Develop a graphical user interface for visualizing the suffix tree or suffix array.
-
Test and debug your tool.
Review the concept of longest common substring
Show steps
Refresh your understanding of longest common substring, a prerequisite for this course.
Browse courses on
String Algorithms
Show steps
Show steps
Show steps
- Go through your notes or textbooks to recall the definition and properties of longest common substring
Organize your notes, assignments, and resources
Show steps
Enhance your learning experience by organizing your course materials effectively.
Show steps
Show steps
Show steps
- Review your lecture notes, assignments, and any additional resources
- Create a system for organizing these materials, such as folders or a digital notebook
Try out this interactive Pattern Matching Explorer
Show steps
Build a foundation with this interactive tool to visualize pattern matching and suffix trees.
Browse courses on
Pattern Matching
Show steps
Show steps
Show steps
- Explore the 'Run Example' section to see the implementation of the algorithm
- Go through the 'Try it Yourself' section to practice pattern matching with suffix trees
Ten other activities
Expand to see all activities and additional details
Show all 13 activities
Watch this video on 'Suffix Trees In 3 minutes'
Show steps
Reinforce your understanding with this concise visual explanation of suffix trees.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Watch the video in its entirety to grasp the fundamental concepts of suffix trees
Review basics of pattern matching
Show steps
Reinforce your knowledge of the basic concepts of pattern matching, which will help you better understand the advanced algorithms covered in the course.
Show steps
Show steps
Show steps
- Read the textbook chapters on pattern matching.
- Work through the practice problems at the end of the chapters.
Solve these practice problems on suffix trees
Show steps
Test your comprehension with a set of challenging practice problems on suffix trees.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Attempt to solve the problems on your own
- Review the provided solutions to identify areas for improvement
Explore tutorials on Burrows-Wheeler Transform
Show steps
Familiarize yourself with the Burrows-Wheeler Transform and its applications, which will enhance your understanding of advanced string algorithms and their use in bioinformatics.
Browse courses on
Burrows-Wheeler Transform
Show steps
Show steps
Show steps
- Find online tutorials or videos that explain the Burrows-Wheeler Transform.
- Follow the tutorials, taking notes and working through the examples.
- Implement a Burrows-Wheeler Transform algorithm in your preferred programming language.
Join a study group to discuss course concepts
Show steps
Engaging in discussions with peers will help you reinforce your understanding of the course concepts, identify areas where you need further clarification, and gain different perspectives.
Show steps
Show steps
Show steps
- Find a study group or create one with classmates.
- Meet regularly to discuss the course material, solve problems, and share insights.
- Take turns leading the discussions and presenting your understanding of the concepts.
Create a diagram explaining the relationship between suffix trees and pattern matching
Show steps
Solidify your understanding by creating a visual representation of the connection between suffix trees and pattern matching.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Brainstorm the key components of suffix trees and pattern matching
- Sketch out a diagram that illustrates how these components interact
- Label the diagram with clear explanations
Solve coding challenges
Show steps
Practice applying the concepts of suffix trees to solve coding challenges, which will help you solidify your understanding and improve your problem-solving skills.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Find a set of coding challenges that focus on suffix trees.
- Solve the challenges, working through the algorithms step by step.
- Review your solutions and identify areas where you can improve your understanding.
Develop a visual representation of a suffix tree
Show steps
Creating a visual representation of a suffix tree will help you gain a deeper understanding of how suffix trees work and how they can be used to perform pattern matching.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Choose a suffix tree construction algorithm.
- Implement the algorithm in your preferred programming language.
- Use your implementation to construct a suffix tree for a given text.
- Develop a visual representation of the suffix tree.
Build a program that implements a suffix tree for a given string
Show steps
Deepen your understanding by implementing a suffix tree from scratch.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Choose a programming language and familiarize yourself with its data structures
- Design and implement the algorithm for constructing a suffix tree
- Test your program with various input strings
Develop a software tool to visualize suffix tree constructions
Show steps
Creating a software tool will provide you with hands-on experience in applying the concepts of suffix trees and suffix arrays, deepening your understanding of their practical applications.
Browse courses on
Suffix Trees
Show steps
Show steps
Show steps
- Design the functionality and user interface of your tool.
- Choose a programming language and development environment.
- Implement the core algorithms for suffix tree and/or suffix array construction.
- Develop a graphical user interface for visualizing the suffix tree or suffix array.
- Test and debug your tool.
Career center
Learners who complete String Processing and Pattern Matching Algorithms will develop knowledge and skills
that may be useful to these careers:
Bioinformatician
Bioinformatician
A Bioinformatician researches biological data and applies computational methods to genomics and molecular biology. The course String Processing and Pattern Matching Algorithms would be beneficial to the career path of a Bioinformatician as this course covers topics such as suffix trees, suffix arrays, and how other brilliant algorithmic ideas help doctors to find differences between genomes. These are all highly relevant topics to the field of bioinformatics.
Data Scientist
Data Scientist
A Data Scientist collects and analyzes large datasets to uncover hidden patterns and insights. The course String Processing and Pattern Matching Algorithms would be beneficial to the career path of a Data Scientist as this course covers topics such as suffix trees, suffix arrays, and the Burrows-Wheeler Transform for compression. These are all highly relevant topics to the field of data science.
Computer Scientist
Computer Scientist
A Computer Scientist researches and develops new computing technologies. The course String Processing and Pattern Matching Algorithms would be beneficial to the career path of a Computer Scientist as this course covers topics such as suffix trees, suffix arrays, and the Burrows-Wheeler Transform for compression. These are all highly relevant topics to the field of computer science.
Software Engineer
Software Engineer
A Software Engineer designs, builds, and maintains computer software. The course String Processing and Pattern Matching Algorithms would be beneficial to the career path of a Software Engineer as this course covers topics such as suffix trees, suffix arrays, and the Burrows-Wheeler Transform for compression. These are all highly relevant topics to the field of computer science.
Network Administrator
Network Administrator
A Network Administrator manages and maintains computer networks. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Network Administrator as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of network administration.
Project Manager
Project Manager
A Project Manager plans, executes, and closes projects. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Project Manager as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of project management.
Product Manager
Product Manager
A Product Manager manages the development and launch of new products. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Product Manager as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of product management.
Technical Writer
Technical Writer
A Technical Writer creates and maintains technical documentation. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Technical Writer as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of technical writing.
Systems Analyst
Systems Analyst
A Systems Analyst analyzes and designs computer systems. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Systems Analyst as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of systems analysis.
Computer Programmer
Computer Programmer
A Computer Programmer writes and maintains computer code. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Computer Programmer as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of computer programming.
Computer Technician
Computer Technician
A Computer Technician installs, maintains, and repairs computers. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Computer Technician as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of computer repair.
Information Security Analyst
Information Security Analyst
An Information Security Analyst protects an organization's computer systems from unauthorized access, use, disclosure, disruption, modification, or destruction. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of an Information Security Analyst as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of information security.
Business Analyst
Business Analyst
A Business Analyst analyzes business processes and develops solutions to improve efficiency. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Business Analyst as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of business analysis.
Database Administrator
Database Administrator
A Database Administrator manages and maintains databases. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Database Administrator as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of database administration.
Web Developer
Web Developer
A Web Developer designs, builds, and maintains websites. The course String Processing and Pattern Matching Algorithms may be beneficial to the career path of a Web Developer as this course covers topics such as suffix trees and suffix arrays. These topics are relevant to the field of web development.
For more career information including salaries, visit:
OpenCourser.com/course/x3d97j/string
Reading list
We've selected eight books
that we think will supplement your
learning. Use these to
develop background knowledge, enrich your coursework, and gain a
deeper understanding of the topics covered in
String Processing and Pattern Matching Algorithms.
Provides a comprehensive overview of bioinformatics algorithms, including string algorithms and their applications in genomics.
Provides a comprehensive introduction to string algorithms, including suffix trees and arrays, and their applications in bioinformatics.
Provides a comprehensive overview of pattern matching in strings, including string algorithms and their applications in computer science.
Save
Provides a practical introduction to string algorithms, with a focus on C++ implementations.
Provides a comprehensive overview of data structures and algorithms, including string algorithms and their applications in computer science.
Provides a comprehensive overview of algorithm design, including string algorithms and their applications in computer science.
Provides a comprehensive overview of computer science, including string algorithms and their applications in computer science.
Provides a comprehensive overview of algorithms, including string algorithms and their applications in computer science.
For more information about how these books relate to this course, visit:
OpenCourser.com/course/x3d97j/string
Share
Similar courses
Here are nine courses similar to
String Processing and Pattern Matching Algorithms.
Algorithms on Strings
OpenCourser.com/course/fvbtd5/algorithms
Algorithms on Strings
Most relevant
Algorithms Data Structures in Java #2 (+INTERVIEW QUESTIONS)
OpenCourser.com/course/u1bfo8/algorithms
Algorithms Data Structures in Java #2 (+INTERVIEW...
Most relevant
Introduction to Java Programming: Fundamental Data Structures and Algorithms
OpenCourser.com/course/ttpbau/introduction
Introduction to Java Programming: Fundamental Data...
Most relevant
Data Structures & Algorithms IV: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms
OpenCourser.com/course/3rrrv9/data
Data Structures & Algorithms IV: Pattern Matching,...
Most relevant
Ordered Data Structures
OpenCourser.com/course/2i4xtc/ordered
Ordered Data Structures
Most relevant
Algorithms Data Structures in Java #1 (+INTERVIEW QUESTIONS)
OpenCourser.com/course/alg19j/algorithms
Algorithms Data Structures in Java #1 (+INTERVIEW...
Most relevant
Algorithms and Data Structures in Python (INTERVIEW Q&A)
OpenCourser.com/course/ejkoch/algorithms
Algorithms and Data Structures in Python (INTERVIEW Q&A)
Most relevant
Advanced Algorithms (Graph Algorithms) in Java
OpenCourser.com/course/oqqhzi/advanced
Advanced Algorithms (Graph Algorithms) in Java
Most relevant
Trees and Graphs: Basics
OpenCourser.com/course/i8v24i/trees
Trees and Graphs: Basics
Most relevant
Effort
8 to 10 hours per week for 4 weeks
Level
Intermediate
Via
edX
Institution
The University of California, San Diego
Instructors
Pavel Pevzner
Michael Levin
Language
English
Transcript
English
This course belongs to a
collection
called
Algorithms and Data Structures. It's comprised of nine courses:
- Algorithmic Design and Techniques
- Data Structures Fundamentals
- Graph Algorithms
- NP-Complete Problems
- String Processing and Pattern Matching Algorithms (viewing)
- Dynamic Programming: Applications In Machine Learning and Genomics
- Graph Algorithms in Genome Sequencing
- Algorithms and Data Structures Capstone
- Introduction to Algorithms
Good to know
Examines string algorithms, which are essential for search engines and personalized medicine, making it highly relevant to tech and healthcare professionals
Taught by Michael Levin and Pavel Pevzner, renowned researchers in bioinformatics, increasing its credibility
Covers advanced topics like suffix trees and the Burrows-Wheeler Transform, appealing to learners with a strong foundation in computer science
Part of the Algorithms and Data Structures MicroMasters program, indicating its rigor and potential for career advancement
May require prerequisites or additional knowledge in computer science, which could pose a barrier for beginners
Our mission
OpenCourser helps millions of learners each year. People visit us to learn workspace skills, ace their exams, and nurture their curiosity.
Our extensive catalog contains over 50,000 courses and twice as many books. Browse by search, by topic, or even by career interests. We'll match you to the right resources quickly.
Find this site helpful? Tell a friend about us.
Affiliate disclosure
We're supported by our community of learners. When you purchase or subscribe to courses and programs or purchase books, we may earn a commission from our partners.
Your purchases help us maintain our catalog and keep our servers humming without ads.
Thank you for supporting OpenCourser.
© 2016 - 2024 OpenCourser