PMC:1570465 / 15646-19297 JSONTXT

{"project":"2_test","denotations":[{"id":"16916460-15546935-1687080","span":{"begin":3090,"end":3092},"obj":"15546935"}],"text":"Integer linear programming formulation\nThe motif finding problem can be formulated as an ILP as follows. For a graph G = (V, E) corresponding to the motif finding problem, where V = V1 ∪ ... ∪ VN and E = {(u, v): u ∈ Vi, v ∈ Vj, i ≠ j}, we introduce a binary decision variable xu for every vertex u, and a binary decision variable yuv for every edge (u, v). Setting xu to 1 corresponds to selecting vertex u for the clique and thus choosing the sequence position corresponding to u in the alignment. Edge variable yuv is set to 1 if both endpoints u and v are selected for the clique. Then the following ILP solves the motif finding problem formulated above:\nMaximize ∑ ( u , v ) ∈ E w u v ⋅ y u v subject to ∑ u ∈ V j x u = 1 for  1 ≤ j ≤ N ( n o d e  constraints ) ∑ u ∈ V j y u v = x v for  1 ≤ j ≤ N , v ∈ V \\ V j ( e d g e  constraints ) x u , y u v ∈ { 0 , 1 } for  u ∈ V , ( u , v ) ∈ E MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqaaeqbdaaaaeaacqqGnbqtcqqGHbqycqqG4baEcqqGPbqAcqqGTbqBcqqGPbqAcqqG6bGEcqqGLbqzaeaadaaeqaqaaiabdEha3naaBaaaleaacqWG1bqDcqWG2bGDaeqaaOGaeyyXICTaemyEaK3aaSbaaSqaaiabdwha1jabdAha2bqabaaabaGaeiikaGIaemyDauNaeiilaWIaemODayNaeiykaKIaeyicI4SaemyraueabeqdcqGHris5aaGcbaaabaGaee4CamNaeeyDauNaeeOyaiMaeeOAaOMaeeyzauMaee4yamMaeeiDaqNaeeiiaaIaeeiDaqNaee4Ba8gabaaabaaabaWaaabeaeaacqWG4baEdaWgaaWcbaGaemyDauhabeaakiabg2da9iabigdaXaWcbaGaemyDauNaeyicI4SaemOvay1aaSbaaWqaaiabdQgaQbqabaaaleqaniabggHiLdaakeaacqqGMbGzcqqGVbWBcqqGYbGCcqqGGaaicqaIXaqmcqGHKjYOcqWGQbGAcqGHKjYOcqWGobGtaeaacqGGOaakcqWGUbGBcqWGVbWBcqWGKbazcqWGLbqzcqqGGaaicqqGJbWycqqGVbWBcqqGUbGBcqqGZbWCcqqG0baDcqqGYbGCcqqGHbqycqqGPbqAcqqGUbGBcqqG0baDcqqGZbWCcqGGPaqkaeaadaaeqaqaaiabdMha5naaBaaaleaacqWG1bqDcqWG2bGDaeqaaOGaeyypa0JaemiEaG3aaSbaaSqaaiabdAha2bqabaaabaGaemyDauNaeyicI4SaemOvay1aaSbaaWqaaiabdQgaQbqabaaaleqaniabggHiLdaakeaacqqGMbGzcqqGVbWBcqqGYbGCcqqGGaaicqaIXaqmcqGHKjYOcqWGQbGAcqGHKjYOcqWGobGtcqGGSaalcqWG2bGDcqGHiiIZcqWGwbGvcqGGCbaxcqWGwbGvdaWgaaWcbaGaemOAaOgabeaaaOqaaiabcIcaOiabdwgaLjabdsgaKjabdEgaNjabdwgaLjabbccaGiabbogaJjabb+gaVjabb6gaUjabbohaZjabbsha0jabbkhaYjabbggaHjabbMgaPjabb6gaUjabbsha0jabbohaZjabcMcaPaqaaiabdIha4naaBaaaleaacqWG1bqDaeqaaOGaeiilaWIaemyEaK3aaSbaaSqaaiabdwha1jabdAha2bqabaGccqGHiiIZcqGG7bWEcqaIWaamcqGGSaalcqaIXaqmcqGG9bqFaeaacqqGMbGzcqqGVbWBcqqGYbGCcqqGGaaicqWG1bqDcqGHiiIZcqWGwbGvcqGGSaalcqGGOaakcqWG1bqDcqGGSaalcqWG2bGDcqGGPaqkcqGHiiIZcqWGfbqraeaaaaaaaa@E7E9@\nThe first set of constraints ensures that exactly one vertex is picked from every graph part, corresponding to one position being chosen from every input sequence. The second set of constraints relates vertex variables to edge variables, allowing the objective function to be expressed in terms of finding a maximum edge-weight clique. An edge is chosen only if it connects two chosen vertices. This formulation is similar to that used by us [41] in fixed-backbone protein design and homology modeling.\nILP itself is NP-hard, but replacing the integrality constraints on the x and y variables with 0 ≤ xu, yuv ≤ 1 gives an LP that can be solved in polynomial time. If the LP solution happens to be integral, it is guaranteed to be optimal for the original ILP and motif finding problem. Non-integral solutions, on the other hand, are not feasible for the ILP and do not translate to a selection of positions for the MSA problem; in these cases, more computationally intensive ILP solvers must be invoked."}