Major Histocompatibility Complex (MHC) molecules play a critical role in the immune system by presenting peptides on the cell surface for recognition by T-cells. Tumor cells often produce MHC peptides with amino acid mutations, known as neoantigens, which evade T-cell recognition, leading to rapid tumor growth. In immunotherapies such as TCR-T and CAR-T, identifying these mutated MHC peptide sequences is crucial. Current mass spectrometry-based peptide identification methods primarily rely on database searching, which fails to detect mutated peptides not present in human databases. In this paper, we propose a novel workflow called NeoMS, designed to efficiently identify both non-mutated and mutated MHC-I peptides from mass spectrometry data. NeoMS utilizes a tagging algorithm to generate an expanded sequence database that includes potential mutated proteins for each sample. Furthermore, it employs a machine learning-based scoring function for each peptide-spectrum match (PSM) to maximize search sensitivity. Finally, a rigorous target-decoy approach is implemented to control the false discovery rates (FDR) of the peptides with and without mutations separately. Experimental results for regular peptides demonstrate that NeoMS outperforms four benchmark methods. For mutated peptides, NeoMS successfully identifies hundreds of high-quality mutated peptides in a melanoma-associated sample, with their validity confirmed by further studies.

Cancer remains a significant global health challenge, responsible for millions of deaths annually. Addressing this issue necessitates the discovery of novel anti-cancer drugs. Anti-cancer peptides (ACPs), with their unique ability to selectively target cancer cells, offer new hope in discovering low side-effect anti-cancer drugs. However, the process of discovering novel ACPs is both time-consuming and costly. Therefore, there is an urgent need for a computational method that can predict whether a given peptide is an ACP and classify its specific functional types. In this paper, we introduce DUO-ACP, a model serving dual roles in ACP prediction: identification and functional type classification. DUO-ACP employs two embedding modules to acquire knowledge about global protein features and local ACP characteristics, complemented by a prediction module. When assessed on two publicly available datasets for each task, DUO-ACP surpasses all existing methods, achieving outstanding results: an ACP identification accuracy of 89.5% and a Macro-averaged AUC of 88.6% in ACP functional type classification. We further interpret the contribution of each part of our model, including the two types of embeddings as well as ensemble learning. On a new curated dataset, the prediction results of DUO-ACP closely match existing literature, highlighting DUO-ACP's generalization capabilities on previously unseen data and displaying the potential capability of discovering novel ACP.

Amyloid light chain (AL) amyloidosis is a disorder characterized by the deposition of antibody light chains in organs. Early and accurate diagnosis of AL amyloidosis is crucial for timely implementation of appropriate treatment strategies. However, existing computational methods for predicting AL amyloidosis often heavily rely on manually extracted features and their performance is less than satisfactory. In this study, we introduce DeepAL, a deep learning-based approach designed to predict AL amyloidosis with high precision. DeepAL utilizes a pre-trained model to extract light chain features and is then fine-tuned with AL amyloidosis knowledge. On two benchmark datasets, DeepAL achieved impressive results with area under the ROC curves (AUCs) of 0.9072 and 0.8919, outperforming previous approaches. Our ablation study shows the use of the pre-trained model can significantly improve identification performance. The code is available at https://github.com/waterlooms/DeepAL.

MOTIVATION: In proteomics, database search programs are routinely used for peptide identification from tandem mass spectrometry data. However, many low-quality spectra cannot be interpreted by any programs. Meanwhile, certain high-quality spectra may not be identified due to incompleteness of the database or failure of the software. Thus, spectrum quality (SPEQ) assessment tools are helpful programs that can eliminate poor-quality spectra before the database search and highlight the high-quality spectra that are not identified in the initial search. These spectra may be valuable candidates for further analyses. RESULTS: We propose SPEQ: a spectrum quality assessment tool that uses a deep neural network to classify spectra into high-quality, which are worthy candidates for interpretation, and low-quality, which lack sufficient information for identification. SPEQ was compared with a few other prediction models and demonstrated improved prediction accuracy. AVAILABILITY AND IMPLEMENTATION: Source code and scripts are freely available at github.com/sor8sh/SPEQ, implemented in Python.

Glycosylation is a frequently observed post-translational modification on proteins. Currently, tandem mass spectrometry (MS/MS) serves as an efficient analytical technique for characterizing structures of oligosaccharides. However, developing effective computational approaches for identifying glycan structures from mass spectra is still a great challenge in glycoproteomics research. In this study, we proposed an approach for matching the input spectra with glycan structures acquired from a glycan structure database by incorporating a de novo sequencing assisted ranking scheme. The proposed approach is implemented as a software tool, GlycoNovoDB, for automated glycan structure identification from HCD MS/MS of glycopeptides. Experimental results showed that GlycoNovoDB can identify glycans effectively and has better performance than our previously proposed de novo sequencing algorithm as well as another software GlycoMaster DB.

A scoring function plays a critical role in software for peptide identification with mass spectrometry. We present a general scoring feature that can be incorporated in the scoring functions of other peptide identification software. The scoring feature is based on the intensity ratios between two adjacent y-ions in the spectrum. A method is proposed to obtain the probability distributions of such ratios, and to calculate the scoring feature based on the distributions. To demonstrate the performance of the method, the new feature is incorporated with X!Tandem [1] , [2] and Novor [3] and significantly improved the database search and de novo sequencing performances on the testing data, respectively.

Mixture spectra occur quite frequently in a typical wet-lab mass spectrometry experiment, which result from the concurrent fragmentation of multiple precursors. The ability to efficiently and confidently identify mixture spectra is essential to alleviate the existent bottleneck of low mass spectra identification rate. However, most of the traditional computational methods are not suitable for interpreting mixture spectra, because they still take the assumption that the acquired spectra come from the fragmentation of a single precursor. In this manuscript, we formulate the mixture spectra de novo sequencing problem mathematically, and propose a dynamic programming algorithm for the problem. Additionally, we use both simulated and real mixture spectra data sets to verify the merits of the proposed algorithm.

Large-scale comparison or similarity search of genomic DNA and protein sequence is of fundamental importance in modern molecular biology. To perform DNA and protein sequence similarity search efficiently, seeding (or filtration) method has been widely used where only sequences sharing a common pattern or "seed" are subject to detailed comparison. Therefore these methods trade search sensitivity with search speed. In this paper, we introduce a new seeding method, called spaced k-mer neighbors, which provides a better tradeoff between the sensitivity and speed in protein sequence similarity search. With the method of spaced k-mer neighbors, for each spaced k-mer, a set of spaced k-mers is selected as its neighbors. These pre-selected spaced k-mer neighbors are then used to detect hits between query sequence and database sequences. We propose an efficient heuristic algorithm for the spaced neighbor selection. Our computational experimental results demonstrate that the method of spaced k-mer neighbors can improve the overall tradeoff efficiency over existing seeding methods.

MOTIVATION: Label-free quantification is an important approach to identify biomarkers, as it measures the quantity change of peptides across different biological samples. One of the fundamental steps for label-free quantification is to match the peptide features that are detected in two datasets to each other. Although ad hoc software tools exist for the feature matching, the definition of a combinatorial model for this problem is still not available. RESULTS: A combinatorial model is proposed in this article. Each peptide feature contains a mass value and a retention time value, which are used to calculate a matching weight between a pair of features. The feature matching is to find the maximum-weighted matching between the two sets of features, after applying a to-be-computed time alignment function to all the retention time values of one set of the features. This is similar to the maximum matching problem in a bipartite graph. But we show that the requirement of time alignment makes the problem NP-hard. Practical algorithms are also provided. Experiments on real data show that the algorithm compares favorably with other existing methods. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In DNA and protein sequence similarity search, seeding (or filtration) has been widely used to trade search sensitivity with search speed. In this paper, a new seeding method, called spaced k-mer neighbors, is introduced to provide a more efficient tradeoff between the speed and sensitivity in protein similarity search. The new method pre-selects a set of spaced k-mers as neighbors, and uses the neighbors to detect hits between the query and database sequences. An efficient heuristic algorithm is proposed for the neighbor selection. We demonstrate that the method can improve the tradeoff efficiency over existing seeding methods.

BACKGROUND: Given n strings s1, …, sn each of length ℓ and a nonnegative integer d, the CLOSEST STRING problem asks to find a center string s such that none of the input strings has Hamming distance greater than d from s. Finding a common pattern in many--but not necessarily all--input strings is an important task that plays a role in many applications in bioinformatics. RESULTS: Although the closest string model is robust to the oversampling of strings in the input, it is severely affected by the existence of outliers. We propose a refined model, the closest string with outliers (CSWO) problem, to overcome this limitation. This new model asks for a center string s that is within Hamming distance d to at least n - k of the n input strings, where k is a parameter describing the maximum number of outliers. A CSWO solution not only provides the center string as a representative for the set of strings but also reveals the outliers of the set.We provide fixed parameter algorithms for CSWO when d and k are parameters, for both bounded and unbounded alphabets. We also show that when the alphabet is unbounded the problem is W[1]-hard with respect to n - k, ℓ, and d. CONCLUSIONS: Our refined model abstractly models finding common patterns in several but not all input strings. We initialize the study of the computability of this model and show that it is sensitive to different parameterizations. Lastly, we conclude by suggesting several open problems which warrant further investigation.

BACKGROUND: Tandem mass spectrometry (MS/MS) has become the primary way for protein identification in proteomics. A good score function for measuring the match quality between a peptide and an MS/MS spectrum is instrumental for the protein identification. Traditionally the to-be-measured peptides are fragmented with the collision induced dissociation (CID) method. More recently, the electron transfer dissociation (ETD) method was introduced and has proven to produce better fragment ion ladders for larger and more basic peptides. However, the existing software programs that analyze ETD MS/MS data are not as advanced as they are for CID. RESULTS: To take full advantage of ETD data, in this paper we develop a new score function to evaluate the match between a peptide and an ETD MS/MS spectrum. Experiments on real data demonstrated that this newly developed score function significantly improved the de novo sequencing accuracy of the PEAKS software on ETD data. CONCLUSION: A new and better score function for ETD MS/MS peptide identification was developed. The method used to develop our ETD score function can be easily reused to train new score functions for other types of MS/MS data.

On participatory Websites, users provide opinions about products, with both overall ratings and textual reviews. In this paper, we propose an approach to accurately estimate feature ratings of the products. This approach selects user reviews that extensively discuss specific features of the products (called specialized reviews), using information distance of reviews on the features. Experiments on real data show that overall ratings of the specialized reviews can be used to represent their feature ratings. The average of these overall ratings can be used by recommender systems to provide feature specific recommendations that better help users make purchasing decisions.

Abstract Motivation: The bottom-up tandem mass spectrometry (MS/MS) is regularly used in proteomics nowadays for identifying proteins from a sequence database. De novo sequencing software is also available for sequencing novel peptides with relatively short sequence lengths. However, automated sequencing of novel proteins from MS/MS remains a challenging problem. Results: Very often, although the target protein is novel, it has a homologous protein included in a known database. When this happens, we propose a novel algorithm and automated software tool, named Champs, for sequencing the complete protein from MS/MS data of a few enzymatic digestions of the purified protein. Validation with two standard proteins showed that our automated method yields >99% sequence coverage and 100% sequence accuracy on these two proteins. Our method is useful to sequence novel proteins or ‘re-sequence’ a protein that has mutations comparing with the database protein sequence. Availability: The software, named Champs (Complete Homology-Assisted Ms/ms Protein Sequencing), and the MS/MS data used in the article, are freely available at http://monod.uwaterloo.ca/champs/. Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

The closest string problem and the closest substring problem are all natural theoretical computer science problems and find important applications in computational biology. Given n input strings, the closest string (substring) problem finds a new string within distance d to (a substring of) each input string and such that d is minimized. Both problems are NP-complete. In this paper we propose new algorithms for these two problems. For the closest string problem, we developed an exact algorithm with time complexity $O(n|\Sigma|^{O(d)})$, where $\Sigma$ is the alphabet. This improves the previously best known result $O(nd^{O(d)})$ and results into a polynomial time algorithm when $d=O(\log n)$. By using this algorithm, a polynomial time approximation scheme (PTAS) for the closest string problem is also given with time complexity $O(n^{O(\epsilon^{-2})})$, improving the previously best known $O(n^{O(\epsilon^{-2}\log\frac{1}{\epsilon})})$ PTAS. A new algorithm for the closest substring problem is also proposed. Finally, we prove that a restricted version of the closest substring problem has the same parameterized complexity as the closest substring, answering an open question in the literature.

Securely authenticating a human user without assistance from any auxiliary device in the presence of powerful passive adversaries is an important and challenging problem. Passive adversaries are those that can passively monitor, intercept, and analyze every part of the authentication procedure, except for an initial secret shared between the user and the server. In this paper, we propose a new secure authentication scheme called predicate-based authentication service (PAS). In this scheme, for the first time, the concept of a predicate is introduced for authentication. We conduct analysis on the proposed scheme and implement its prototype system. Our analytical data and experimental data illustrate that the PAS scheme can simultaneously achieve a desired level of security and user friendliness.

If Kolmogorov complexity [25] measures information in one object and Information Distance measures information shared by two objects, how do we measure information shared by many objects? This paper provides an initial pragmatic study of this fundamental data mining question. Firstly, Em(x1,x2,...,xn) is defined to be the minimum amount of thermodynamic energy needed to convert from any xi to any xj. With this definition several theoretical problems have been solved. Second, our newly proposed theory is applied to select a comprehensive review and a specialized review from many reviews: (1) Core feature words, expanded words and dependent words are extracted respectively. (2) Comprehensive and specialized reviews are selected according to the information among them. This method of selecting a single review can be extended to select multiple reviews as well. Finally, experiments show that this comprehensive and specialized review mining method based on our new theory can do the job efficiently.

MOTIVATION: The next generation sequencing technologies are generating billions of short reads daily. Resequencing and personalized medicine need much faster software to map these deep sequencing reads to a reference genome, to identify SNPs or rare transcripts. RESULTS: We present a framework for how full sensitivity mapping can be done in the most efficient way, via spaced seeds. Using the framework, we have developed software called ZOOM, which is able to map the Illumina/Solexa reads of 15x coverage of a human genome to the reference human genome in one CPU-day, allowing two mismatches, at full sensitivity. AVAILABILITY: ZOOM is freely available to non-commercial users at http://www.bioinfor.com/zoom

This paper is an enquiry into the interaction between multiple description coding (MDC) and network routing. We are mainly concerned with rate-distortion optimized network flow of a multiple description (MD) source from multiple servers to multiple sinks. We aim at maximizing a collective metric of the quality of source reconstruction at all sinks, by optimally routing the MD source streams from the server nodes to the sinks. This problem turns out to be very different from conventional maximum network flow. The objective function involves not only the flow volume but also the diversity of the flow contents (i.e., distinction of descriptions), hence, the term rainbow network flow (RNF). For a general network topology, a general fidelity function, and an arbitrary distribution of MDC descriptions on the servers, we prove the RNF problem to be Max-SNP-hard. However, the problem becomes tractable in many practical scenarios, such as when MDC is balanced with descriptions of the same length and importance, when all source nodes have the complete set of MDC descriptions, and when the network topology is a tree or has only one sink. Polynomial-time RNF algorithms are developed for these cases.

Similarity metric is important in many applications. In some applications, it is desirable to normalize the similarity metric so as to yield a more meaningful insight of the situation, for example, in comparison of long genomic sequences and comparative gene prediction. In extending the content of a previous work involving formal definition of the concept known as similarity, we give new formulas for normalizing similarity metrics which satisfy the formal definition of the normalized similarity metric. We also describe how these formulas may be utilized in an appropriate application domain in which the use of normalized similarity metric is desirable.

In this paper, we study the issue of sensor network deployment using limited mobility sensors. By limited mobility, we mean that the maximum distance that sensors are capable of moving to is limited. Given an initial deployment of limited mobility sensors in a field clustered into multiple regions, our deployment problem is to determine a movement plan for the sensors to minimize the variance in number of sensors among the regions and simultaneously minimize the sensor movements. Our methodology to solve this problem is to transfer the nonlinear variance/movement minimization problem into a linear optimization problem through appropriate weight assignments to regions. In this methodology, the regions are assigned weights corresponding to the number of sensors needed. During sensor movements across regions, larger weight regions are given higher priority compared to smaller weight regions, while simultaneously ensuring a minimum number of sensor movements. Following the above methodology, we propose a set of algorithms to our deployment problem. Our first algorithm is the optimal maximum flow-based (OMF) centralized algorithm. Here, the optimal movement plan for sensors is obtained based on determining the minimum cost maximum weighted flow to the regions in the network. We then propose the simple peak-pit-based distributed (SPP) algorithm that uses local requests and responses for sensor movements. Using extensive simulations, we demonstrate the effectiveness of our algorithms from the perspective of variance minimization, number of sensor movements, and messaging overhead under different initial deployment scenarios.

An important phase of sensor networks operation is deployment of sensors in the field of interest. Critical goals during sensor networks deployment include coverage, connectivity, load balancing, etc. A class of work has recently appeared, where mobility in sensors is leveraged to meet deployment objectives. In this paper, we study deployment of sensor networks using mobile sensors. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. We call such sensors as flip-based sensors. Given an initial deployment of flip-based sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage and minimize the number of flips. We propose a minimum-cost maximum-flow-based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors due to the limitations on sensor mobility

In packet switched networks receivers can get packets of a multiple description code (MDC) from different sources for enhanced QoS and robust transmission. The quality achieved by a decoder increases in the number of distinct rather than the total number of packets received. This property makes the problems of optimizing network flows and transmission strategies for MDC, called rainbow network problems, very different from those of conventional network flow and management. Two interesting problems: rainbow network flow and rainbow multicast, are formulated and treated. The rainbow network flow problem of maximizing the number of distinct packets received, constrained by edge capacities, is shown to be NP-hard in multisource-multisink setting. But it can be reduced to conventional maximum network flow problem in the case of single sink, hence becomes solvable in polynomial time. Rainbow multicast problem is about coordinating multiple servers for minimum expected distortion at one or a set of clients. Although being seemingly intractable in general, some variants of the problem have analytical solutions

In this paper, we study the issue of mobility based sensor networks deployment. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. Given an initial deployment of sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage, and minimize the number of flips. We propose a minimum-cost maximum-flow based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage, and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors, due to the limitations on sensor mobility

UNLABELLED: New ideas, spaced seeds and gapped alignment before 6-frame translation are implemented for translated homology search in tPatternHunter. The new software compares favorably with tBLASTx. AVAILABILITY: The software is free to academics at http://www.bioinformaticssolutions.com/downloads/ph-academic/ CONTACT: [email protected].

A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new "normalized information distance," based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric . This theory forms the foundation for a new practical tool. To evidence generality and robustness, we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.

MOTIVATION: Genome analysis suggests that tandem duplication is an important mode of evolutionary novelty by permitting one copy of each gene to drift and potentially to acquire a new function. With more and more genomic sequences available, reconstructing duplication history has received extensive attention recently. RESULTS: An efficient method is presented for inferring the duplication history of tandemly repeated sequences based on the model proposed by Fitch (1977). We validate the method by using simulation results and real data sets of mucin genes, ZNF genes, and olfactory receptors genes. The agreement with conclusions drawn by other biological researchers strongly indicates that our method is efficient and robust. AVAILABILITY: The program is available by request.

Consider two sets of strings, ${\cal B}$ (bad genes) and ${\cal G}$ (good genes), as well as two integers $d_b$ and $d_g$ ($d_b\leq d_g$). A frequently occurring problem in computational biology (and other fields) is to find a (distinguishing) substring s of length L that distinguishes the bad strings from good strings, i.e., such that for each string $s_i\in {\cal B}$ there exists a length-L substring t i of s i with $d(s, t_i)\leq d_b$ (close to bad strings), and for every substring u i of length L of every string $g_i\in {\cal G}$, $d(s, u_i)\geq d_g$ (far from good strings). We present a polynomial time approximation scheme to settle the problem; i.e., for any constant $\epsilon >0$, the algorithm finds a string s of length L such that for every $s_i\in {\cal B}$ there is a length-L substring t i of s i with $d(t_i, s)\leq (1+\epsilon) d_b$, and for every substring u i of length L of every $g_i\in {\cal G}$, $d(u_i, s)\geq (1-\epsilon) d_g$ if a solution to the original pair ($d_b\leq d_g$) exists. Since there is a polynomial number of such pairs $(d_b,d_g)$, we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems.

Abstract Summary: While achieving the best compression ratios for DNA sequences, our new DNACompress program significantly improves the running time of all previous DNA compression programs. Availability: http://dna.cs.ucsb.edu/DNACompress Contact: [email protected]@cs.ucsb.edu * To whom correspondence should be addressed.

MOTIVATION: Genomics and proteomics studies routinely depend on homology searches based on the strategy of finding short seed matches which are then extended. The exploding genomic data growth presents a dilemma for DNA homology search techniques: increasing seed size decreases sensitivity whereas decreasing seed size slows down computation. RESULTS: We present a new homology search algorithm 'PatternHunter' that uses a novel seed model for increased sensitivity and new hit-processing techniques for significantly increased speed. At Blast levels of sensitivity, PatternHunter is able to find homologies between sequences as large as human chromosomes, in mere hours on a desktop. AVAILABILITY: PatternHunter is available at http://www.bioinformaticssolutions.com, as a commercial package. It runs on all platforms that support Java. PatternHunter technology is being patented; commercial use requires a license from BSI, while non-commercial use will be free.

The problem of finding a center string that is "close" to every given string arises in computational molecular biology and coding theory. This problem has two versions: the Closest String problem and the Closest Substring problem. Given a set of strings S = { s 1 , s 2 , ..., s n }, each of length m , the Closest String problem is to find the smallest d and a string s of length m which is within Hamming distance d to each s i ε S . This problem comes from coding theory when we are looking for a code not too far away from a given set of codes. Closest Substring problem, with an additional input integer L , asks for the smallest d and a string s , of length L , which is within Hamming distance d away from a substring, of length L , of each si. This problem is much more elusive than the Closest String problem. The Closest Substring problem is formulated from applications in finding conserved regions, identifying genetic drug targets and generating genetic probes in molecular biology. Whether there are efficient approximation algorithms for both problems are major open questions in this area. We present two polynomial-time approximation algorithms with approximation ratio 1 + ε for any small ε to settle both questions.

Arc-annotated sequences are useful in representiug the structural information of RNA sequences. Typically, RNA secondary and tertiary structures could be represented by a set of nested arcs and a set of crossing arcs, respectively. As the specified RNA functions are determined by the specified molecular confirmation and therefore the specified secondary and tertiary structures, the comparison between RNA secondary and tertiary structures have received much attention recently. In this paper, we propose the notion of edit distance to measure the similarity between two RNA secondary and tertiary structures, by incorporating the various edit operations performing on both bases and arcs (base-pairs). Several algorithms are presented to compute the edit distance two RNA sequences with various arc structures and under various score schemes, either exactly or approximately. Preliminary experimental tests confirm that our definition of edit distance and the computation model are among the most reasonable ones ever studied in the literature.

Multiple sequence alignment is one of the most important problems in computational biology.Because of its notorious difficulties, aligning sequences within a constant band is a popular practice in bioinformatics with good results [17; 13; 14; 15; 1; 3; 6; 20; 18].However, the problem is still NP-hard for multiple sequences.In this paper, we present polynomial time approximation schemes (PTAS) for multiple sequence alignment within a constant band, tinder standard models of SP alignment and consensus (star) alignment.The algorithms work for very general score schemes.In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.

This paper studies various algorithmic issues in reconstructing a species tree from gene trees under the duplication and the mutation costmodel. This is a fundamental problem in computational molecular biology. Our main results are as follows. A linear time algorithm is presented for computing all the losses in duplications associated with the least common ancestor mapping from a gene tree to a species tree. This answers a problem raised recently by Eulenstein, Mirkin, and Vingron [J. Comput. Bio., 5 (1998), pp. 135--148]. The complexity of finding an optimal species tree from gene trees is studied. The problem is proved to be NP-hard for the duplication cost and for the mutation cost. Further, the concept of reconciled trees was introduced by Goodman et al. and formalized by Page for visualizing the relationship between gene and species trees. We show that constructing an optimal reconciled tree for gene trees is also NP-hard. Finally, we consider a general reconstruction problem and show it to be NP-hard even for the well-known nearest neighbor interchange distance. A new and efficiently computable metric is defined based on the duplication cost. We show that the problem of finding an optimal species tree from gene trees is NP-hard under this new metric but it can be approximated within factor 2 in polynomial time. Using this approximation result, we propose a heuristic method for finding a species tree from gene trees with uniquely labeled leaves under the duplication cost. Our experimental tests demonstrate that when the number of species is larger than 15 and gene trees are close to each other, our heuristic method is significantly better than the existing program in Page's GeneTree 1.0 that starts the search from a random tree.

Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems.We solve three main open questions in this area.Assume that we are given n DNA sequences 81,., an.The Consensus Patterns problem, which has been widely studied in bioinformatics research [26,16,12,25,4, 6, 15, 22, 24, 271, in its simplest form, asks for a region of length L in each ai, and a median string s of length L so that the total Hamming distance from B to these regions is minimized.We show the problem is NPhard and give a polynomial time approximation scheme (PTAS) for it.We also give a PTAS for the problem under the original measure of [26,16,12, 251.As an interesting application of OUT analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important star alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence.The Closest String problem [Z, 3, 7, 9, 181 asks for the smallest d and a string d which is within Hamming distance d to each a;.The problem is NP-hard [7, 181.[3] gives a polynomial time algorithm for constant d.For super-logarithmic d, [Z, 91 give efficient approximation algorithms using linear program relaxation techniques.The best polynomial time approximation has ratio $ for all d, given by [18] ([9] also independently claimed the $ ratio but only for super-logarithmic d).We settle the problem with a PTAS.We then give the fist nontrivial better-than-2 approximation with ratio 2 -& for the more eluive Closest Substring problem [IS]: find a string d of length L such that, for each i, s is within Hamming distance d from home substring, of length L, of si.

and Losses Bin Ma: Ming Lif and