# Questions tagged [bioinformatics]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
312 views

### Introductory books on nature sciences behind bioinformatics

My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background ...
407 views

### Seeking popular science book on bioinformatics or computational genomics

An intelligent 15-year-old I know is interested in both computer science and genetics. I told her that these fields make an excellent combination. I'd like to give her a book on bioinformatics or ...
105 views

### Borrowing bioinformatic methods in other fields

Have the bioinformatic methods like sequence analysis, genome annotation, comparative genomics (and many others), been applied to solve problems outside the field of bioinformatics?
330 views

### Mutual information and moment generating functions

I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough ...
286 views

### Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?

A common modification to the Needleman-Wunsch to reduce running time is to only fill in the cells along a diagonal band of the matrix (slides 27/28). Let 2d + 1 represent the width of the band. Then ...
124 views

### Sequence Alignment with Skips

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
714 views

### A framework to capture common variation of sequence alignments

The global alignment problem can be generalized by setting the cost of some boundary gaps to 0. Gaps at both end in both strings have 0 cost, then we get the semiglobal alignment. Gaps are at the ...
460 views

### Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
122 views

### Compact mapping from an involuted set

Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative ...
228 views

### Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works. However, I have merely seen hand-waving explanations for the ...
119 views

### Recovering species from a phylogenetic tree

This question is based on Problem 2 from the 'Bioinformatics contest' of 2018. Given a phylogenetic tree $T=(V,E)$ of $n$ vertices, in which some leaves are assigned an integer color $c$ from $[1,n]$,...
46 views

### Minimum number of nucleotides to force duplicate substring

There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T. Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of ...
546 views

### Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?

I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores: +1 for match (regardless of base), -1 gap penalty and -1 for a mismatch. Given two ...
700 views

### How is n-gram different from k-mer?

How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and ...
51 views

### What is an approximation factor for the Greedy Motif Search algorithm?

What is approximation factor for the Greedy Motif Search algorithm? I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native ...
774 views

### Programming languages for genetic engineering [closed]

I'm interested in getting a Ph.D. and would love to work on a project such the GEC project at Microsoft Research, which studies the application of programming languages for synthetic biology and ...
190 views

### Interleave two arrays such that collisions are minimised (dynamic programming) [closed]

This is a fascinating bioinformatics dynamic programming that I am solving. I am not looking for an answer to the problem, but rather any algorithms, research papers, or other pointers that could be ...
115 views

### optimal lifted phylogenetic alignment - how to improve time complexity?

optimal lifted alignment - is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$). The algorithm then assigns strings to the ...
120 views

### Is the dynamic programming pairwise alignment algorithm considered greedy?

I'm a freshman in Computer Science and I'm studying bioinformatics sequence alignment algorithms. My understanding of a greedy algorithm is one that takes the best decision for a particular instance ...
227 views

### Waterman-Smith-Beyer Algorithm

I am having trouble understanding the affine gap penalty in the following example - Waterman-Smith-Beyer Algorithm: \begin{align*} D_{0,0} &= 0\\ D_{0,j} &= g(j)\\ D_{i,0} &= g(i)\\ \...
65 views

### a variant of Fitch's algorithm when it is known that one path has cost 0?

Fitch's algorithm solves the small parsimony problem - given tree topology and leaf labels, but not internal node labels, find best internal node labels (i.e. best score) for that tree. The score is ...
116 views

### proving that local sequence alignment can be done in linear space

according to the Smith-Waterman setup, I have 2 string sequences S and T, and I want to identify their respective subsequences $\alpha$ and $\beta$ whose global alignment have maximum score over all ...
81 views

### Multiple sequence Progressive alignment example using five sequences

I tried to find sources that explain multiple sequence alignment with an example using progressive alignment, but I couldn't find one. I actually know till creating a guide tree, after creating a ...
500 views

### How different is the working of SNN (Spiking Neural Network) as compared to a real Neuron System in biological systems?

Assuming its one step closer to realism as compared to ANN, DNNs and other Neural Network models, what are the primary differences between a real neuron system and SNN?
34 views

### String matching and bioinformatics [closed]

I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.
392 views

### multiple sequence alignment using HMM and simulated annealing

Can anyone help me with Multiple Sequence Alignment (MSA) using Hidden Markov Model (HMM) by giving an example or a reference except these 2 references: 1-Eddy, Sea.R., et al.Multiple alignment using ...
184 views

### center star alignment induces optimal alignments on pairs with the center string?

I'm trying to follow the center star algorithm error analysis - section 6.5.3. They claim that for the center string $S_1$ the distance induced by the algorithm $d(1, j)$ is always equal the optimal ...
60 views

### Graph theoretical approach to compare n pair of variables along a set of interval

I am dealing a bioinformatics problem and need help in approaching it in the right direction. I have a set of variables that represent different kinds of genomic data and are real valued. I am trying ...