Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00453-007-9068-8 | Algorithmica |
Keywords | Field | DocType |
Secondary Structure,Maximum Weight,Local Prediction,Horizontal Edge,Connector Edge | Combinatorics,Algorithm,Heuristics,Set packing,Ab initio,Metric space,Hydrogen bond,Protein secondary structure,Mathematics,Protein structure | Journal |
Volume | Issue | ISSN |
53 | 1 | 0178-4617 |
Citations | PageRank | References |
1 | 0.40 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Piotr Berman | 1 | 32 | 3.31 |
| Jieun Jeong | 2 | 14 | 2.46 |