Sequence Alignment problem | function to find out the minimum penalty ; table for storing optimal substructure answers ; initialising the table ; calculating the minimum penalty ; Reconstructing the solution $l = $n + $m ; maximum possible length ; Final answers for the respective strings $xans [ $l + 1 ] ; $yans [ $l + 1 ] ; ; Since we have assumed the answer to be n + m long , we need to remove the extra gaps in the starting id represents the index from which the arrays xans , yans are useful ; Printing the final answer ; input strings ; initialising penalties of different types ; calling the function to calculate the result
< ? php function getMinimumPenalty ( $ x , $ y , $ pxy , $ pgap ) { $ dp [ $ n + $ m + 1 ] [ $ n + $ m + 1 ] = array ( 0 ) ; for ( $ i = 0 ; $ i <= ( $ n + $ m ) ; $ i ++ ) { $ dp [ $ i ] [ 0 ] = $ i * $ pgap ; $ dp [ 0 ] [ $ i ] = $ i * $ pgap ; } for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { if ( $ x [ $ i - 1 ] == $ y [ $ j - 1 ] ) { $ dp [ $ i ] [ $ j ] = $ dp [ $ i - 1 ] [ $ j - 1 ] ; } else { $ dp [ $ i ] [ $ j ] = min ( $ dp [ $ i - 1 ] [ $ j - 1 ] + $ pxy , $ dp [ $ i - 1 ] [ $ j ] + $ pgap , $ dp [ $ i ] [ $ j - 1 ] + $ pgap ) ; } } } $ i = $ m ; $ j = $ n ; $ xpos = $ l ; $ ypos = $ l ; while ( ! ( $ i == 0 $ j == 0 ) ) { if ( $ x [ $ i - 1 ] == $ y [ $ j - 1 ] ) { $ xans [ $ xpos -- ] = $ x [ $ i - 1 ] ; $ yans [ $ ypos -- ] = $ y [ $ j - 1 ] ; $ i -- ; $ j -- ; } else if ( $ dp [ $ i - 1 ] [ $ j - 1 ] + $ pxy == $ dp [ $ i ] [ $ j ] ) { $ xans [ $ xpos -- ] = $ x [ $ i - 1 ] ; $ yans [ $ ypos -- ] = $ y [ $ j - 1 ] ; $ i -- ; $ j -- ; } else if ( $ dp [ $ i - 1 ] [ $ j ] + $ pgap == $ dp [ $ i ] [ $ j ] ) { $ xans [ $ xpos -- ] = $ x [ $ i - 1 ] ; $ yans [ $ ypos -- ] = ' _ ' ; $ i -- ; } else if ( $ dp [ $ i ] [ $ j - 1 ] + $ pgap == $ dp [ $ i ] [ $ j ] ) { $ xans [ $ xpos -- ] = ' _ ' ; $ yans [ $ ypos -- ] = $ y [ $ j - 1 ] ; $ j -- ; } } while ( $ xpos > 0 ) { if ( $ i > 0 ) $ xans [ $ xpos -- ] = $ x [ -- $ i ] ; else $ xans [ $ xpos -- ] = ' _ ' ; } while ( $ ypos > 0 ) { if ( $ j > 0 ) $ yans [ $ ypos -- ] = $ y [ -- $ j ] ; else $ yans [ $ ypos -- ] = ' _ ' ; } $ id = 1 ; for ( $ i = $ l ; $ i >= 1 ; $ i -- ) { if ( $ yans [ $ i ] == ' _ ' && $ xans [ $ i ] == ' _ ' ) { $ id = $ i + 1 ; break ; } } echo " Minimum ▁ Penalty ▁ in ▁ " . " aligning ▁ the ▁ genes ▁ = ▁ " ; echo $ dp [ $ m ] [ $ n ] . " STRNEWLINE " ; echo " The ▁ aligned ▁ genes ▁ are ▁ : STRNEWLINE " ; for ( $ i = $ id ; $ i <= $ l ; $ i ++ ) { echo $ xans [ $ i ] ; } echo " STRNEWLINE " ; for ( $ i = $ id ; $ i <= $ l ; $ i ++ ) { echo $ yans [ $ i ] ; } return ; } $ gene1 = " AGGGCT " ; $ gene2 = " AGGCA " ; $ misMatchPenalty = 3 ; $ gapPenalty = 2 ; getMinimumPenalty ( $ gene1 , $ gene2 , $ misMatchPenalty , $ gapPenalty ) ; ? >