Given the stem dictionary D s , interrupted stems are constructed using maximum weight independent set (MWIS) calculations with the confidence indicators as stem weights (Supplementary Algorithm 1). Using confidence c instead of local free energy gives better results in the MWIS calculation. First, it implicitly penalizes the formation of long bulge or internal loops. Second, the confidence is a relative measurement based on the whole folding ensemble. Only stems s i with confidence cðs i Þ ! 1 Â E À3 are considered as base pairs below this threshold are unlikely to participate in non-crossing secondary structure formation (55) . This cutoff step also significantly reduces runtime for longer sequences. Each stem s i 2 D s has two (left and right) endpoints a i and b i and is represented as an interval on the line. First, the sorted endpoints list for all stems is constructed and scanned from left to right. If a right endpoint is discovered, a candidate list of stems nested in the interval