Consistent Sets of Secondary Structures in Proteins

Piotr Berman, Jieun Jeong

    Research output: Contribution to journalArticlepeer-review


    Ab initio predictions of secondary structures in proteins have to combine local predictions, based on short fragments of the protein sequence, with consistency restrictions, as not all locally plausible predictions may be simultaneously true. We use the fact that secondary structures are patterns of hydrogen bonds and that a single residue can participate in hydrogen bonds of at most one secondary structure. Consistency of fixed-sized pieces of secondary structures is the easiest to approximate and we formalize it as 1-2 matching problem. Consistency of entire secondary structures is a version of set packing. We also investigate how to form a simple problem if we add the requirement that the secondary structure and the loops that connect them fit together in a metric space. Every problem that we investigated is MAX-SNP hard and it has a constant factor approximation. Computational experience suggests that in biological instances, we can find nearly optimal solutions using heuristics.

    Original languageEnglish (US)
    Pages (from-to)16-34
    Number of pages19
    JournalAlgorithmica (New York)
    Issue number1
    StatePublished - Jan 1 2009

    All Science Journal Classification (ASJC) codes

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics


    Dive into the research topics of 'Consistent Sets of Secondary Structures in Proteins'. Together they form a unique fingerprint.

    Cite this