PMC:1624833 / 7872-10581 JSONTXT

{"project":"2_test","denotations":[{"id":"16952321-7497125-1695220","span":{"begin":1292,"end":1294},"obj":"7497125"},{"id":"16952321-3294162-1695221","span":{"begin":2130,"end":2132},"obj":"3294162"},{"id":"16952321-7497125-1695222","span":{"begin":2346,"end":2348},"obj":"7497125"},{"id":"16952321-14633395-1695223","span":{"begin":2352,"end":2354},"obj":"14633395"},{"id":"16952321-10421525-1695223","span":{"begin":2352,"end":2354},"obj":"10421525"}],"text":"2 Related work\nA binary matrix has the Consecutive Ones Property (COP) for rows if its columns can be permuted such that all the ones in each row are consecutive [22]. See Figure 2 for an example of a matrix with the COP. Determining whether a matrix has the COP and computing the permutation of the columns that proves this property has applications in a number of areas including testing for graph planarity [22] and recognizing interval graphs [22,23]. Booth and Leuker [22] describe a data structure called the PQ tree which they use to represent all legal permutations of column orderings in a matrix with the COP property. They prove that the PQ tree and the correct column permutation can be computed in time linear in the number of ones in the matrix.\nFigure 2 An illustration of the COP. Figure 2(a): A matrix that has the COP with the first two columns highlighted. Figure 2(b): Swapping the first two columns of the matrix demonstrates that the matrix has the COP. 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].\nAlgorithms for constructing physical maps from hybridization data typically exploit the Lander-Waterman model [26], which assumes that clones are distributed uniformly across the chromosome and that probes are distributed according to independent Poisson processes. Some algorithms make additional domain-specific assumptions [24,25,27-29]. For instance, Batzoglou and Istrail compute an ordering whose length is at most twice the length of the optimal ordering under the requirement that each clone match a probe that does not hybridize to any other clone. None of these algorithms are applicable to our problem since the biclusters we want to lay out may not have the required properties."}