Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [bioinformatics]

The tag has no usage guidance.

0
votes
0answers
14 views

Global Sequence Alignment: possible gap, match, and mismatch values?

Can gap/match/mismatch be 0? Is it possible for match/mismatch to both be 0, or does mismatch need to be less than match? Do they have to be integers, or can they be float values?
2
votes
2answers
105 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]$,...
4
votes
1answer
153 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 ...
3
votes
1answer
107 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 ...
3
votes
1answer
41 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 ...
1
vote
0answers
149 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)\\ \...
0
votes
1answer
212 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 ...
1
vote
0answers
42 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 ...
4
votes
0answers
101 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 ...
1
vote
0answers
44 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 ...
4
votes
0answers
192 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 ...
1
vote
1answer
66 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 ...
0
votes
1answer
139 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 ...
1
vote
1answer
86 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 ...
0
votes
1answer
432 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?
0
votes
0answers
59 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 ...
2
votes
1answer
346 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 ...
2
votes
1answer
395 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 ...
0
votes
0answers
26 views

Are there any algorithms or researches on finding local alignments in partially ordered sequences?

The question is a bit unclear, so let me explain. Finding local alignments in sequences like protein sequence is a well studied area in bioinformatics, and I do not think there is any lack of ...
1
vote
0answers
70 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 ...
2
votes
1answer
768 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 ...
-1
votes
1answer
80 views

Selecting a M.S. in CS focus [closed]

I need to pick a focus in my Masters program. The running candidates are Networking Bioinformatics Data mining Computer Image Recognition In order to avoid this becoming a discussion, I'd be ...
6
votes
1answer
104 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?
3
votes
1answer
547 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 ...
9
votes
1answer
340 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 ...
5
votes
1answer
257 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 ...
11
votes
4answers
302 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 ...