OpenCourser brand icon
Sign in
We may earn an affiliate commission when you visit our partners.
Course image
Course image
edX logo

String Processing and Pattern Matching Algorithms

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.

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:

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
Enroll now

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

Syllabus

Traffic lights

Read about what's good
what should give you pause
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

Create your own learning path. Save this course to your list so you can find it easily later.
Save

Reviews summary

String algorithms: deep, challenging, applied

According to students, this course offers a deep dive into string processing and pattern matching algorithms, particularly praised for its coverage of suffix trees and suffix arrays. Learners consistently highlight the real-world applications, especially in bioinformatics and genomics, making complex concepts tangible. While the assignments are challenging yet rewarding, many emphasize that the course is highly theoretical and demands a strong foundational knowledge in algorithms and discrete mathematics, making it more suitable for advanced learners. Some suggest that the lecture pace can feel rushed in later sections and that more interactive coding examples would enhance the learning experience.
Problem sets effectively test understanding.
"The programming assignments were tough but fair and really solidified my understanding."
"The problem sets were engaging, yet some solutions could have benefited from more detailed explanations."
"The assignments truly test your understanding."
"The exercises were good for applying concepts..."
Highlights practical use in genomics and biology.
"I especially appreciated the real-world applications in bioinformatics; it made the theoretical concepts tangible."
"The practical applications demonstrated, particularly in genomics, were fascinating and highly relevant."
"The application to bioinformatics was interesting."
"I found the applications to genomics particularly fascinating."
Provides extensive theoretical understanding of algorithms.
"This course provided an incredibly deep dive into string algorithms."
"The strength of this course lies in its theoretical depth on string algorithms."
"It thoroughly covered important topics like suffix arrays, which were particularly well-explained."
"I found the explanations top-notch, making this one of the best algorithms courses I've taken."
Lectures can be dense, and later parts feel rushed.
"The pace in later weeks felt rushed."
"I found some of the proofs and theoretical derivations to be quite dense and hard to grasp."
"I found the lectures to be very dense, and the presentation style could be dry at times."
"The presentation sometimes assumes too much, making it hard to follow without external resources."
Emphasizes theory, with less hands-on coding guidance.
"Disappointed with the lack of practical coding examples beyond the assignments."
"The course is very theoretical... I expected more hands-on implementation guidance for real-world scenarios."
"It felt like a deep dive into academia, not practical application."
"I wish there were more interactive elements or coding exercises directly within the lectures."
Requires a strong background in CS and mathematics.
"The course is definitely for advanced learners, not beginners."
"I struggled with the assignments related to bioinformatics applications; perhaps a stronger background in biology/genomics would have helped."
"I recommend having a strong background in discrete mathematics and algorithms before attempting it."
"I felt they assumed a bit too much prior knowledge in advanced data structures."

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
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
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
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'
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
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
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
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
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
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
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
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
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
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.

Career center

Learners who complete String Processing and Pattern Matching Algorithms will develop knowledge and skills that may be useful to these careers:
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.
See salaries and explore the career path for Bioinformatician
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.
See salaries and explore the career path for Data Scientist
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.
See salaries and explore the career path for Software Engineer
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.
See salaries and explore the career path for Computer Scientist
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.
See salaries and explore the career path for Web Developer
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.
See salaries and explore the career path for Technical Writer
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.
See salaries and explore the career path for Business Analyst
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.
See salaries and explore the career path for Product 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.
See salaries and explore the career path for Project Manager
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.
See salaries and explore the career path for Information Security Analyst
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.
See salaries and explore the career path for Database Administrator
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.
See salaries and explore the career path for Systems Analyst
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.
See salaries and explore the career path for Network Administrator
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.
See salaries and explore the career path for Computer Programmer
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.
See salaries and explore the career path for Computer Technician

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.
Cover image
Bioinformatics Algorithms
Save
Provides a comprehensive overview of bioinformatics algorithms, including string algorithms and their applications in genomics.
BIOINFORMATICS ALGORITHMS
Hardcover
$$$
BIOINFORMATICS ALGORITHMS,VOL.II
Paperback
$$
Cover image
Parameter Advising for Multiple Sequence Alignment
Save
Provides a comprehensive introduction to string algorithms, including suffix trees and arrays, and their applications in bioinformatics.
Parameter Advising for Multiple Sequence Alignment...
Kindle Edition
$$
Cover image
Combinatorial Pattern Matching
Save
Provides a comprehensive overview of pattern matching in strings, including string algorithms and their applications in computer science.
Combinatorial Pattern Matching: 4th Annual...
Paperback
$$$
Combinatorial Pattern Matching: 16th Annual...
Paperback
$$$
Combinatorial Pattern Matching: 8th Annual...
Paperback
$$$
Combinatorial Pattern Matching: 13th Annual...
Paperback
$$$
Combinatorial Pattern Matching: Third Annual...
Perfect Paperback
$$$
Cover image
Algorithms
Save
Provides a practical introduction to string algorithms, with a focus on C++ implementations.
Algorithms
Paperback
Check
Algorithms
Kindle Edition
Check
Cover image
Data Structures and Algorithms in Java
Save
Provides a comprehensive overview of data structures and algorithms, including string algorithms and their applications in computer science.
Data Structures and Algorithms in Java
Paperback
$$$$
Data Structures and Algorithms in Java, 6th Edition
Kindle Edition
$$$
Cover image
The Algorithm Design Manual
Save
Provides a comprehensive overview of algorithm design, including string algorithms and their applications in computer science.
The Algorithm Design Manual (Texts in Computer...
Hardcover
$$$
The Algorithm Design Manual
Paperback
$$$
The Algorithm Design Manual (Texts in Computer...
Kindle Edition
$$
The Algorithm Design Manual
Kindle Edition
$$$
Cover image
Foundations of Computer Science
Save
Provides a comprehensive overview of computer science, including string algorithms and their applications in computer science.
Foundations of Computer Science: C Edition...
Hardcover
$$$$
Cover image
Introduction to Algorithms, fourth edition
Save
Provides a comprehensive overview of algorithms, including string algorithms and their applications in computer science.
Introduction to Algorithms, fourth edition
Hardcover
$$$$
Introduction to Algorithms, fourth edition
Kindle Edition
$$$

Share

Help others find this course page by sharing it with your friends and followers:
Facebook
LinkedIn
Reddit
X
Link
Email

Similar courses

Here are nine courses similar to String Processing and Pattern Matching Algorithms.
Algorithms on Strings
Most relevant
Introduction to Regular Expressions in SQL
Most relevant
Advanced SAS Programming Techniques
Most relevant
Functional Programming Principles in Scala
Most relevant
C#/.NET - 50 Essential Interview Questions (Mid Level)
Most relevant
Advanced Scala and Functional Programming | Rock the JVM
Most relevant
Finding Mutations in DNA and Proteins (Bioinformatics VI)
Most relevant
Scala 3: Just What You Need
Most relevant
Advanced Algorithms in Java
Most relevant

edX Buyer Protection & Guarantee

Verified partner policies & purchase protections

World-Class University Partner
Free Trial & Audit

Free Audit Track Available

Free audit track available for most courses, giving open access to video lectures, course readings, and assignments at no charge.

Return & Refund Policy

14-Day Full Refund Window

14-day full refund available up to 14 days after course start or 14 days after payment (whichever comes second, up to 6 months max), provided verified certificate has not yet been earned.

Buyer Protections

Verified Academic & Industry Partner

University-backed credentials authored by elite institutions like Harvard, MIT, and Oxford, with tamper-proof certificate verification.

Key Purchase Protections
Free audit track for open learning access
14-day money-back guarantee on verified certificates
Prestigious university credentials (Harvard, MIT)
Automatic unenrollment refund process via dashboard
OpenCourser Verified Partner Policy details last reviewed: 2026-10-22
Course image
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:
  1. Algorithmic Design and Techniques
  2. Data Structures Fundamentals
  3. Graph Algorithms
  4. NP-Complete Problems
  5. String Processing and Pattern Matching Algorithms (viewing)
  6. Dynamic Programming: Applications In Machine Learning and Genomics
  7. Graph Algorithms in Genome Sequencing
  8. Introduction to Algorithms
  9. Algorithms and Data Structures Capstone
Traffic lights
Read about what's good
what should give you pause
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
Share this
Share to help others discover this course.
Facebook LinkedIn X Reddit Link Email
Begin learning today
Enroll now to gain full access to String Processing and Pattern Matching Algorithms.
Enroll now
Save for later
Add this course to your list. Find it anytime.
Save
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 - 2025 OpenCourser