Stack Exchange Network

Stack Exchange network consists of 175 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
7

As a previous response stated, it is not an absolute requirement that you study biology in order to do bioinformatics. However, if you wish to have a background understanding of the foundational concepts such as genes, RNA, DNA, etc. then a good introductory biology book should provide everything that you need. Molecular biology is not the kind of topic ...


6

The moment generating function $M_X$ is a property of a random variable $X$. It's defined by the expected value of $e^{tX}$ (where $t$ is the argument). Since the exponential function $e^x = \sum_0^\infty \frac{x^n}{n!}$ contains all natural powers of its argument as a summand, the expected value of a sum is the sum of the expected values ($\mathbb{E}(\...


5

Of course! The perfect example is Gusfield book. Many of string algorithms came from bioinformatics. For example, sequence analysis algorithms are used in text editors. PS: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Dan Gusfield


5

Despite the different uses of the algoritms, and the various names, I personally would say this is a single algorithm, with different variations. To make this answer more readable, I will add some details. The basic algoritm global alignment (aka Needleman-Wunsch, below left) compares two strings $x=x_1\dots x_m$ and $y = y_1 \dots y_n$ (with match/mismatch ...


4

Your optimal alignment seems to be an optimal local alignment, the best substring match. Needleman-Wunsch is for global alignment. With the simple program by Eddy that you can find on the internet I have determined a global score of 0. This is better than the gobal score you get: -5 (for 10 gaps and 5 matches). Sequence X: GCATGCU Sequence Y: GATTACA ...


4

The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is repeated. The latter can be obtained from a de Bruijn sequence with $n=3$ and $k=4$. The length of this sequence is $k^n=64$ symbols. A de Bruijn sequence is a cyclic ...


3

I can give two candidate solutions for your specific situation. Approach #1: parity This only works if $k$ is odd. Notice that if $k$ is odd, the parity of $f(x)$ is the reverse of the parity of $x$. In other words, the xor of the bits of $f(x)$ is the complement of the xor of the bits of $x$. This suggests an encoding. Define $g(x)$ to choose between $...


3

Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more common in computational genomics. See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.


3

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible. Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \cdots$ respectively. Let $x$ be one of $a,b,\cdots$ such that $c(x)$ is the maximum. Let $\sigma$ be the sum of all $c(i)$ where $i$ goes through $a, b, \cdots$ ...


3

As someone who came from a computer science background and led a team developing a product involving bioinformatics I can sympathize with the challenge of picking up the domain - but it is a fascinating area to work in. As @JCEHR has pointed out, it is not an absolute requirement to study biology but it is helpful to start to pick up some of the principals. ...


2

this is a very broad question so am going to answer it with decent lists found across the internet most of which are sorted by some criteria (eg bestsellers, top review counts, etc). also there are so many bioinformatics books now and one strategy might be to simply go with your favorite publisher. there are some that come up often in CS areas eg O'Reilly. ...


2

Algorithm: Find the Lowest Common Ancestor of each color: this node can act as source for the color. Starting from each source, paint all their descendants doing a Depth First Search (the search must stop when another LCA is visited). If the root of the tree is not painted, paint it and all its unpainted descendants (via DFS) with the color of the highest ...


2

I present an algorithm for the tree case. The algorithm solves the problem in two 'passes' through the tree: first from leaves to root, then from the root to the leaves. Algorithm: First, we augment our tree $T$ with the additional field $v.subcolors$ for each vertex $v$. This field should contain the set of all colors present in the subtree rooted at $v$ (...


2

You are correct, the number of insertions/deletions $d$ is not constrained (only) by the bandwidth. However, the algorithm only uses the fact that if we know $d$, then the path must stay within the $2d+1$ band. This band does not have to be tight: a zigzag path would indeed fit within a much narrower band. You may wonder why the smallest bandwidth (which ...


2

Consider a node $x$ with children $x_1,\ldots,x_d$, and denote by $N(v)$ the number of leaves in the subtree $T(v)$ rooted at $v$. We can implement the processing of $x$ as follows: Go over $1 \leq i \leq d$: Choose a leaf $f_i \in T(x_i)$ as the label of $x$ and $x_i$. For all $j \neq i$, choose the leaf $f_j \in T(x_j)$ that minimizes $D(f_i,f_j) + d(...


2

No. Rather, the DP algorithm for pairwise sequence alignment1 is an instance of backtracking. What makes it superior to naïve exhaustive search is that it abandons potential solutions as soon as it can prove that it is going to be sub-optimal (each field in the DP matrix considers only the optimal previous sub-alignment), and it computes partial results ...


2

As a Computer Scientist who did their minor in Biochemistry, my recommendation would be Larry Gonick's Cartoon guide to Genetics. This is not a joke. I know of several respectable Bioinformaticians who learnt genetics this way. The book explains most of what, if not everything, you will need to know and supplies the most intuitive visuals to wrap your mind ...


1

Quoting Master’s Thesis in Computer Science by Finn Rosenbech Jensen0, Dec. 2010, Greedy Motif algorithm approximation factor, using common superstring1 and its linear approximation2, was proved it cannot be better then 2. Using proof by Kaplan and Shafir3 author shows that $\mid t_{greedy}\mid = 3.5 * OPT(S)$. [0]: Master thesis by Rosenbech Jensen [1]: ...


1

There are different types of spiking neural network models: Hodgkin-Huxley: models the processes within a neuron with electrical parts. This results in differential equations with 4 variables (capacity of the membrane, resistance of the ion channels, balance potentials, openings of the ion channels). Leaky integrate and Fire (LIF): Probably the simplest SNN;...


1

I choose to reply in an answer rather than a comment because I think that is actually the proper answer to your question (and it is too long for a comment anyway). Style If you intend to do research and write papers for an audience, then you should learn to be easy to read. Any improvement costs only once to you, and saves time and energy to each one of ...


1

My response does not provide exact data that you are looking for, but I am going to suggest a few sources from where you can capture the data. Firstly, if you have some time to choose between those fields, take a course in each if possible and see for yourself whether you actually enjoy or not. I have had cases where I thought I was excited about a subject, ...


1

As others told you: it depends a little on the book that you will be using, as well as on the topics taught. Sometimes it will be rather self explanatory. However in order to be better prepared (and get used to the terminology) look at some primers on the web, like Preparata: A Biology Primer for Computer Scientists. Do we have colleagues, or is the "...


Only top voted, non community-wiki answers of a minimum length are eligible