"packing" .
"single residue" .
_:N322becbb71fc467f9a8718749f132391 .
"Algorithmica" .
"approximation" .
.
"factor approximation" .
_:N1452026a3b4e4c98b81d6056968177f4 .
"article" .
"ab initio predictions" .
.
"pieces" .
"Jieun" .
_:N1452026a3b4e4c98b81d6056968177f4 "doi" .
"local predictions" .
.
"version" .
"consistent set" .
.
.
.
"Springer Nature" .
_:N44100f1977f443ba96b6ba5e6000500f .
"residues" .
.
"heuristics" .
_:N44100f1977f443ba96b6ba5e6000500f "53" .
_:Nd8086e6013ba414cb5fb8a76c0735f70 .
"metric spaces" .
.
.
_:N985997c0da8f4421b9542a1c0f374699 "Springer Nature - SN SciGraph project" .
.
.
.
.
"Berman" .
.
"1432-0541" .
.
"matching problem" .
.
"biological instances" .
"computational experience" .
"short fragments" .
"patterns" .
"prediction" .
.
"solution" .
"optimal solution" .
"restriction" .
"problem" .
"Consistent Sets of Secondary Structures in Proteins" .
"simple problems" .
_:Nd8086e6013ba414cb5fb8a76c0735f70 .
.
"The Pennsylvania State University, University Park, PA, USA" .
"loop" .
"sequence" .
.
.
"https://doi.org/10.1007/s00453-007-9068-8" .
.
.
_:N985997c0da8f4421b9542a1c0f374699 .
.
"protein" .
.
"2007-11-10" .
"fragments" .
"set packing" .
"instances" .
"plausible predictions" .
"0178-4617" .
.
"MAX SNP" .
"2007-11-10" .
.
.
.
.
_:N1452026a3b4e4c98b81d6056968177f4 "10.1007/s00453-007-9068-8" .
_:N6549bf00be5a4b609b08060db31c3cd9 .
"2022-09-02T15:52" .
.
"fact" .
"hydrogen bonds" .
"secondary structure" .
_:N44100f1977f443ba96b6ba5e6000500f .
.
"initio predictions" .
"bonds" .
"Physical Chemistry (incl. Structural)" .
"Abstract\nAb 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.\n\nWe 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.\n\nEvery 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." .
"structure" .
_:N198fb5696ed848ebb382db295279acc4 _:N322becbb71fc467f9a8718749f132391 .
.
"Piotr" .
"consistency" .
"https://scigraph.springernature.com/explorer/license/" .
_:N198fb5696ed848ebb382db295279acc4 .
_:N1452026a3b4e4c98b81d6056968177f4 .
.
_:N6549bf00be5a4b609b08060db31c3cd9 "dimensions_id" .
.
"Chemical Sciences" .
.
.
"space" .
"set" .
_:N985997c0da8f4421b9542a1c0f374699 .
"consistency restrictions" .