00000caa a22000003i 4500 UP-1685594773862408503 Buklod 20210324115723.0 m | | ta 210324s2019 xx r |||| u|eng d (iLib)UPBAG-00039569122 STII-DOST BAG rda eng ARTICLE-2874 Clemente, Jhoirene B. author. Reoptimization of the consensus pattern problem under pattern length modification by Jhoirene B. Clemente, Proceso L. Fernandez Jr., Richelle Ann B. Juayong, Jasmine A. Malinao, Ivy D. Ordanel, and Henry N. Adorna. 2019. pages 535-549 illustrations 26 cm text rdacontent unmediated rdamedia volume rdacarrier Includes bibliographical references (pages 547-549) In Bioinformatics, finding conserved regions in genomic sequences remains to be a challenge not just because of the increasing size of genomic data collected but because of the hardness of the combinatorial model of the problem. One problem formulation is called the Consensus Pattern Problem (CPP). Given a set of t n-length strings S = {S1,..., St} defined over some constant size alphabet Σ and an integer l, where l ≤ n, the objective of CPP is to find an l-length string v and a set of l-length substrings si of each Si in S such that the total sum of d(si, v) is minimized for all 1 ≤ i ≤ t. Here d(x, y) denotes the Hamming distance between the two strings x and y. It is known that CPP is NP-hard i.e., unless P = NP, there is no polynomial-time algorithm that produces an optimal solution for CPP. In this study, we investigate a combinatorial setting called reoptimization in finding an approximate solution for this problem. We seek to identify whether a specific additional information can help in solving CPP. Specifically, we deal with the following reoptimization scenario. Suppose we have an optimal l-length consensus substring of a given set of sequences S. How can this information be beneficial in obtaining an (l + k)-length and (l ? k)-length consensus for S? In this paper, we show that the reoptimization variant of the problem is still computationally hard even with k = 1. In response, we present four algorithms that make use of the given optimal solution ? we prove that the first three algorithms produce solutions with quality that is bounded from above by an additive error that grows as the parameter k increases, while the fourth algorithm achieves a guaranteed approximation ratio. It has been shown that there is no efficient polynomial-time approximation scheme for CPP (Boucher 2015). In this paper, we show that we can save (−(+)+)((+)) steps in computation from the original running time of the known polynomial-time approximation scheme for CPP. (Author's abstract) Computer science. Approximation. Consensus pattern. Ptas. Reoptimization. Ordanel, Ivy D. author. Malinao, Jasmine A. author. Juayong, Richelle Ann B. author. Fernandez, Proceso L. Jr. author. Adorna, Henry N. author. The Philippine Journal of Science Vol. 148, no. 3, September 2019. Request full-text access via UPB University Library through https://forms.gle/KZjBv7aRtY6jiL5E9 (viewed 24 March 2021) FI UPBAG UPBAG-MAIN ARTICLE-2874 Analytics