The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The identification of peptides from tandem mass spectra is an important part of many high-throughput proteomics pipelines. In the high-throughput setting, the spectra are typically identified using software that matches tandem mass spectra with putative peptides from amino-acid sequence databases. The effectiveness of these search engines depends heavily on the completeness of the amino-acid sequence...
Haplotype inference problem asks for a set of haplotypes explaining a given set of genotypes. Popular software tools for haplotype inference (e.g., PHASE, HAPLOTYPER) as well as new algorithms recently proposed for perfect phylogeny inference (DPPH) are often not well scalable. When the number of sites (SNP’s) comes to thousands these tools often cannot deliver answer in reasonable time even if the...
We present a new integer programming formulation for the haplotype inference by pure parsimony (HIPP) problem. Unlike a previous approach to this problem [2], we create an integer program whose size is polynomial in the size of the input. This IP is substantially smaller for moderate-sized instances of the HIPP problem. We also show several additional constraints, based on the input, that can be added...
We study the single individual SNP haplotype reconstruction problem. We introduce a simple heuristic and prove experimentally that is very fast and accurate. In particular, when compared with a dynamic programming of [8] it is much faster and also more accurate. We expect Fast Hare to be very useful in practical applications. We also introduce a combinatorial problem related to the SNP haplotype reconstruction...
Recent studies have shown that the chromosomal recombination only takes places at some narrow hotspots. Within the chromosomal region between these hotspots (called haplotype block), little or even no recombination occurs, and a small subset of SNPs (called tag SNPs) is sufficient to capture the haplotype pattern of the block. In reality, the tag SNPs may be genotyped as missing data, and we may fail...
In this paper we present a more efficient algorithm for comparison of minisatellites which has complexity O(n’3+ m’3 + mn’2+ nm’2 +mn) where n and m are the lengths of the maps and n’ and m’ are the sizes of run-length encoded maps. We show that this algorithm makes a significant improvement for the real biological data, dividing the computing time by a factor 30 on a significant set of data.
This paper considers the problem of inferring the optimal nested arc-annotation of a sequence given another nested arc-annotated sequence by maximizing the weighted alignment between the bases and arcs in the two sequences. The problem has a direct application in predicting the secondary structure of an RNA sequence given a closely related sequence whose secondary structure is already known. The currently...
We present a mathematical framework for anchoring inglobal multiple alignment. Our framework uses anchors that are hits to spaced seeds and identifies anchors progressively, using a phylogenetic tree. We compute anchors in the tree starting at the root and going to the leaves, and from the leaves going up. In both cases, we compute thresholds for anchors to minimize errors. One innovative aspect of...
In this paper we propose a chaining method that can align a draft genomic sequence against a finished genome. We introduce the use of an overlap tree to enhance the state information available to the chaining procedure in the context of sparse dynamic programming, and demonstrate that the resulting procedure more accurately penalizes the various biological rearrangements. The algorithm is tested on...
Translation initiation sites (TIS) are important signals in cDNA sequences. Many research efforts have tried to predict TIS in cDNA sequences. In this paper, we propose using mixture Gaussian models to predict TIS in cDNA sequences. Some new global measures are used to generate numerical features from cDNA sequences, such as the length of the open reading frame downstream from ATG, the number of other...
Computational heuristics are the primary methods for reconstruction of phylogenetic trees on large datasets. Most large-scale phylogenetic analyses produce numerous trees that are equivalent for some optimization criteria. Even using the best heuristics, it takes significant amount of time to obtain optimal trees in simulation experiments. When biological data are used, the score of the optimal tree...
It has been observed that the short nucleotide sequences in a variable region, representing species level diversity in a set of 16S rDNA sequences carries the genus specific signature. In this study our aim is to assess the relationship of residues at different positions and thereby obtain consensus patterns using different statistical tools. If such patterns are found genus-specific then it would...
The problem of reconstructing the duplication history of a set of tandemly repeated sequences was first introduced by Fitch (1977). Many recent works deal with this problem, showing the validity of the unequal recombination model proposed by Fitch, describing numerous inference algorithms, and exploring the combinatorial properties of these new mathematical objects, which are duplication trees (DT)...
In practice, one is often faced with incomplete phylogenetic data, such as a collection of partial trees or partial splits. This paper poses the problem of inferring a phylogenetic super-network from such data and provides an efficient algorithm for doing so, called the Z-closure method. Application to a set of five published partial gene trees relating different fungal species illustrates the usefulness...
We explore the problem of designing oligonucleotides that help locate organisms along a known phylogenetic tree. We develop a suffix-tree based algorithm to find such short sequences efficiently. Our algorithm requires O(Nm) time and O(N) space in the worst case where m is the number of the genomes classified by the phylogeny and N is their total length. We implemented our algorithm and used it to...
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two novel operations, called node fusion and edge fusion, besides the tree edit operations of deletion, insertion and relabelling classically used in the literature. This allows us to address some serious limitations of the more traditional tree edit operations when the trees represent RNAs...
Hidden Markov models (HMMs) are often used for biological sequence annotation. Each sequence element is represented by states with the same label. A sequence should be annotated with the labeling of highest probability. Computing this most probable labeling was shown NP-hard by Lyngsø and Pedersen [9]. We improve this result by proving the problem NP-hard for a fixed HMM. High probability labelings...
The problem of finding conserved motifs given a set of DNA sequences is among the most fundamental problems in computational biology, with important applications in locating regulatory sites from co-expressed genes. Traditionally, two classes of approaches are used to address the problem: sample-driven approaches focus on finding the locations of the motif instances directly, while pattern-driven...
We consider the problem of finding the optimal pair of string patterns for discriminating between two sets of strings, i.e. finding the pair of patterns that is best with respect to some appropriate scoring function that gives higher scores to pattern pairs which occur more in the strings of one set, but less in the other. We present an O(N2) time algorithm for finding the optimal pair...
Consider the following problem: Find the shortest pattern that does not occur in a given text. To make the problem non-trivial, the pattern is required to consist only of characters that occur in the text. This problem can be solved easily in linear time using the suffix tree of the text. In this paper, we study an extension of this problem, namely the missing patterns problem: Find the shortest pair of patterns...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.