Questions tagged [bioinformatics]

The tag has no usage guidance.

32 questions
Filter by
Sorted by
Tagged with
1answer
458 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 ...
1answer
79 views

Can I find all the common subsequences between 2 sequences by using dynamic programming?

I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one. Thank you.
0answers
26 views

data structures/ Classes for RNA & DNA

In bioinformatics they study biological data. I have seen codes dealing with DNA sequences. However, they are treated as string literal. I was wondering if there were data structures or classes in OOP ...
1answer
39 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.
1answer
77 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 ...
1answer
586 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. ...
0answers
198 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 ...
1answer
128 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 ...
1answer
108 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?
0answers
248 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 ...
2answers
121 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]$,...
1answer
340 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 ...
1answer
49 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 ...
0answers
247 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)\\ \...
1answer
156 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 ...
0answers
72 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 ...
0answers
140 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 ...
0answers
125 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 ...
1answer
188 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 ...
1answer
119 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 ...
1answer
509 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?
0answers
61 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 ...
1answer
850 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 ...
1answer
594 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 ...
0answers
27 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 ...
0answers
82 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 ...
1answer
479 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 ...
1answer
778 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 ...
1answer
94 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 ...
1answer
820 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 ...
1answer
398 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 ...
4answers
344 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 ...