Glossary

Noncrossing matching

A matching in a graph is noncrossing if when the graph's nodes are arranged in a circle, none of the edges of the matching cross each other.

Shown below are the only two possible noncrossing perfect matchings of the basepair edges in the bonding graph corresponding to the RNA string "UAGCGUGAUCAC".

Noncrossing Perfect Matching

Counting all noncrossing perfect matchings in complete graphs yields the Catalan numbers, whereas counting all noncrossing matchings in complete graphs yields the Motzkin numbers.

Welcome to Rosalind!

Rosalind is a platform for learning bioinformatics through problem solving.
Please login with Google/Twitter/Facebook or register a new account.