PMC:1570465 / 24414-31121
Annnotations
{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1570465","sourcedb":"PMC","sourceid":"1570465","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1570465","text":"Tighter constraints for clique-bounds DEE\nFor a vertex u ∈ Vi and every other Vj, an edge has to connect u to some v ∈ Vj in any alignment. When calculating Fu, we can constrain its value by considering three-way alignments and requiring that the vertices in the best star(u) chosen as neighbors of u in graph parts other than Vj are also good matches to v. Performing this computation for every pair of u, Vj and considering every edge incident on u would be too costly. Therefore, we only consider such three-way alignments for every vertex u ∈ Vi and the next part Vi+1 of the graph (with the last and first parts paired). Essentially, this procedure shifts the emphasis onto edges, allowing better alignments and bounds, and yet eliminates vertices by considering the best edge incident on it.\nFor a given edge (u, v) with endpoints u ∈ Vi and v ∈ Vi+1 we consider an adjacent double star with two centers at u and v, and sharing all the endpoints xj in the other graph parts, denoted as dstar(u, v); the weight of such a dstar(u, v) is 2wuv+∑j≠ij≠i+1(wuxj+wvxj) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqaIYaGmcqWG3bWDdaWgaaWcbaGaemyDauNaemODayhabeaakiabgUcaRmaaqadabaGaeiikaGIaem4DaC3aaSbaaSqaaiabdwha1jabdIha4naaBaaameaacqWGQbGAaeqaaaWcbeaakiabgUcaRiabdEha3naaBaaaleaacqWG2bGDcqWG4baEdaWgaaadbaGaemOAaOgabeaaaSqabaGccqGGPaqkaSqaauaabeqaceaaaeaacqWGQbGAcqGHGjsUcqWGPbqAaeaacqWGQbGAcqGHGjsUcqWGPbqAcqGHRaWkcqaIXaqmaaaabaaaniabggHiLdaaaa@4EE6@. Now consider a clique {u1 ∈ V1, ..., uN ∈ VN} of some value C*, and the sum of its double stars:\n∑ i = 1 N ( 2 w u i u i + 1 + ∑ j ≠ i j ≠ i + 1 ( w u j u i + w u j u i + 1 ) ) = 2 ∑ i = 1 N ∑ j ≠ i w u j u i ( 5 ) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaaeWbqaaiabcIcaOiabikdaYiabdEha3naaBaaaleaacqWG1bqDdaWgaaadbaGaemyAaKgabeaaliabdwha1naaBaaameaacqWGPbqAcqGHRaWkcqaIXaqmaeqaaaWcbeaakiabgUcaRmaaqafabaGaeiikaGIaem4DaC3aaSbaaSqaaiabdwha1naaBaaameaacqWGQbGAaeqaaSGaemyDau3aaSbaaWqaaiabdMgaPbqabaaaleqaaOGaey4kaSIaem4DaC3aaSbaaSqaaiabdwha1naaBaaameaacqWGQbGAaeqaaSGaemyDau3aaSbaaWqaaiabdMgaPjabgUcaRiabigdaXaqabaaaleqaaOGaeiykaKIaeiykaKcaleaafaqabeGabaaabaGaemOAaOMaeyiyIKRaemyAaKgabaGaemOAaOMaeyiyIKRaemyAaKMaey4kaSIaeGymaedaaaqab0GaeyyeIuoaaSqaaiabdMgaPjabg2da9iabigdaXaqaaiabd6eaobqdcqGHris5aOGaeyypa0JaeGOmaiZaaabCaeaadaaeqbqaaiabdEha3naaBaaaleaacqWG1bqDdaWgaaadbaGaemOAaOgabeaaliabdwha1naaBaaameaacqWGPbqAaeqaaaWcbeaaaeaacqWGQbGAcqGHGjsUcqWGPbqAaeqaniabggHiLdaaleaacqWGPbqAcqGH9aqpcqaIXaqmaeaacqWGobGta0GaeyyeIuoakiaaxMaacaWLjaWaaeWaceaacqaI1aqnaiaawIcacaGLPaaaaaa@7C24@\nThis sum is equal to 4C*, as each edge (ui, uj) is counted four times. We define Fuv with for an edge (u, v) with endpoints u ∈ Vi and v ∈ Vi+1 as\nFuv can be viewed as the weight of the best dstar centered at the pair of vertices u, v (or edge (u, v)) and it is the best possible contribution to any alignment, if the edge (u, v) was required to be a part of the alignment. We define Fu for u ∈ Vi and Fi∗ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGgbGrdaqhaaWcbaGaemyAaKgabaGaey4fIOcaaaaa@3038@ for part i similarly to the above definitions as\nF u = max v ∈ V i + 1 F u v ( 7 ) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGgbGrdaWgaaWcbaGaemyDauhabeaakiabg2da9maaxababaGagiyBa0MaeiyyaeMaeiiEaGhaleaacqWG2bGDcqGHiiIZcqWGwbGvdaWgaaadbaGaemyAaKMaey4kaSIaeGymaedabeaaaSqabaGccqWGgbGrdaWgaaWcbaGaemyDauNaemODayhabeaakiaaxMaacaWLjaWaaeWaceaacqaI3aWnaiaawIcacaGLPaaaaaa@446A@\nF i ∗ = max u ∈ V i F u ( 8 ) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGgbGrdaqhaaWcbaGaemyAaKgabaGaey4fIOcaaOGaeyypa0ZaaCbeaeaacyGGTbqBcqGGHbqycqGG4baEaSqaaiabdwha1jabgIGiolabdAfawnaaBaaameaacqWGPbqAaeqaaaWcbeaakiabdAeagnaaBaaaleaacqWG1bqDaeqaaOGaaCzcaiaaxMaadaqadiqaaiabiIda4aGaayjkaiaawMcaaaaa@41FB@\nFu is the value of the best dstar centered on vertex u ∈ Vi and some vertex v ∈ Vi+1, and Fi∗ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGgbGrdaqhaaWcbaGaemyAaKgabaGaey4fIOcaaaaa@3038@ is the value of the best dstar centered on any pair of vertices u ∈ Vi and v ∈ Vi+1.\nFor any clique {u1 ∈ V1, ..., uN ∈ VN} of value C* in the graph, by Equations 5–8 we have\n4 C ∗ ≤ ∑ i = 1... N F u i u i + 1 ≤ ∑ i = 1... N F u i ≤ ∑ i = 1... N F i ∗ ( 9 ) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqaI0aancqWGdbWqdaahaaWcbeqaaiabgEHiQaaakiabgsMiJoaaqafabaGaemOray0aaSbaaSqaaiabdwha1naaBaaameaacqWGPbqAaeqaaSGaemyDau3aaSbaaWqaaiabdMgaPjabgUcaRiabigdaXaqabaaaleqaaaqaaiabdMgaPjabg2da9iabigdaXiabc6caUiabc6caUiabc6caUiabd6eaobqab0GaeyyeIuoakiabgsMiJoaaqafabaGaemOray0aaSbaaSqaaiabdwha1naaBaaameaacqWGPbqAaeqaaaWcbeaaaeaacqWGPbqAcqGH9aqpcqaIXaqmcqGGUaGlcqGGUaGlcqGGUaGlcqWGobGtaeqaniabggHiLdGccqGHKjYOdaaeqbqaaiabdAeagnaaDaaaleaacqWGPbqAaeaacqGHxiIkaaaabaGaemyAaKMaeyypa0JaeGymaeJaeiOla4IaeiOla4IaeiOla4IaemOta4eabeqdcqGHris5aOGaaCzcaiaaxMaadaqadiqaaiabiMda5aGaayjkaiaawMcaaaaa@6583@\nThen Equation 3, with 2C* replaced by 4C*, can be used to eliminate vertices in the same way as before, eliminating a vertex z in a particular graph part if Fz, the value of its best adjacent dstar, is insufficient considering best possible contributions from all other graph parts. For best pruning results the value of C* should be as high as possible; we choose C* as the clique weight induced by the best overall dstar.","divisions":[{"label":"title","span":{"begin":0,"end":41}},{"label":"p","span":{"begin":42,"end":797}},{"label":"p","span":{"begin":798,"end":1745}},{"label":"p","span":{"begin":1746,"end":2975}},{"label":"p","span":{"begin":2976,"end":3122}},{"label":"p","span":{"begin":3123,"end":3721}},{"label":"p","span":{"begin":3722,"end":4264}},{"label":"p","span":{"begin":4265,"end":4786}},{"label":"p","span":{"begin":4787,"end":5256}},{"label":"p","span":{"begin":5257,"end":5346}},{"label":"p","span":{"begin":5347,"end":6283}}],"tracks":[]}