PMC:1624833 / 8849-9890 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1624833","sourcedb":"PMC","sourceid":"1624833","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1624833","text":"Researchers have studied a number of generalizations of the COP problem; however, most of these generalizations are NP-complete or NP-Hard. For example, seeking the column ordering for a non-COP matrix that minimizes the number of gaps between the ones in each row can be reduced to the traveling salesman problem [24]. An important application of generalizations of the COP is physical mapping of chromosomes with probes. We can represent physical mapping data as a binary matrix where the rows represent clones (short overlapping sections of a chromosome), the columns represent DNA probes, and a cell in the matrix has a one if the corresponding probe hybridizes to the corresponding clone. Constructing a physical map of the chromosome is equivalent to finding an ordering of the probes (with probes repeated, if necessary) such that all the probes matching a clone appear consecutively and the total length of the ordering is as small as possible. As mentioned earlier, Batzoglou and Istrail prove that this problem is MAXSNP-Hard [25].","tracks":[{"project":"2_test","denotations":[{"id":"16952321-7497125-1695220","span":{"begin":315,"end":317},"obj":"7497125"}],"attributes":[{"subj":"16952321-7497125-1695220","pred":"source","obj":"2_test"}]}],"config":{"attribute types":[{"pred":"source","value type":"selection","values":[{"id":"2_test","color":"#ec939b","default":true}]}]}}