h*****g
发帖数: 312 | 1 9.7 A circus is designing a tower routine consisting of people standing atop
one another’s shoulders. For practical and aesthetic reasons, each person
must be both shorter and lighter than the person below him or her. Given the
heights and weights of each person in the circus, write a method to compute
the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from to... 阅读全帖 |
|
h*****g
发帖数: 312 | 2 9.7 A circus is designing a tower routine consisting of people standing atop
one another’s shoulders. For practical and aesthetic reasons, each person
must be both shorter and lighter than the person below him or her. Given the
heights and weights of each person in the circus, write a method to compute
the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from to... 阅读全帖 |
|
s****n
发帖数: 1237 | 3 Give you two sequences of length N, how to find the max window of matching
patterns. The patterns can be mutated.
For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (
ABCD from seq1 and DBCA from seq2). 起始位置无需相同。
我一点头绪都没有，就想出了brutal force的办法。对方说可以利用都是N的特性，可
以sort，还是不懂。请教一下应该怎么做。 |
|
A*********r
发帖数: 564 | 4 我怎么觉得没有那么复杂啊，貌似复杂度就是sort的复杂度 。。
用楼主的例子:
seq1: ABCDEFG
seq2: DBCAPFG
可以得到seq2中每个字母在seq1对应的坐标依次为， O（n)可以实现吧。
3 1 2 0 -1 5 6
P字母没有在seq1里面出现，所以标记为-1, 然后sort这个坐标组里面足用-1分割开的
每个段，变为
0 1 2 3 -1 5 6
然后找最长的strictly increment 的一组数就可以了。。
关于这个间隔sort的可行性和复杂度，可以再讨论一下。。
( |
|
h**k
发帖数: 3368 | 5 Give you two sequences of length N, how to find the max window of matching
patterns. The patterns can be mutated.
For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (
ABCD from seq1 and DBCA from seq2). 起始位置无需相同。
这个我知道有O(nlogn)的算法，不知道是否有O(n)的算法。 |
|
t****a
发帖数: 1212 | 6 这题怎么用greedy来做呢？DP的话是n*m计算量
memoize dp的解
(defn is-match [str1 str2]
(let [str1a (str str1 \a)
str2a (str str2 \a)
n1 (count str1a)
n2 (count str2a)
seq2 (apply concat (repeat n1 (range n2 -1 -1)))
seq1 (mapcat #(repeat n2 %) (range n1 -1 -1))
]
(do
(def is-match-rec
(memoize
(fn [i1 i2]
(let [l1 (- n1 i1)
l2 (- n2 i2)]
(cond (and (== 0 l1) (== 0 l2)) true
(or (=... 阅读全帖 |
|
t****a
发帖数: 1212 | 7 尝试了，可以的。如果recursion可以表示为sequence的情形下例如fib数列，就可以用
lazy sequence来实现stackless trampline。
(declare fib2)
(defn fib1 [a b]
(lazy-seq (cons a (fib2 b (+ a b)))))
(defn fib2 [a b]
(lazy-seq (cons a (fib1 b (- a b)))))
(def fib-seq2 (fib1 0.0 1.0))
(nth fib-seq2 100000) ; it works |
|
g******1
发帖数: 295 | 8 For the following two sequences, I am doing blastn on Seq2 against Seq1
blastn -task blastn-short -outfmt "6 nident"
Seq1: ATTAGAWACCCBDGTAGTCC
Seq2: ATTAGATACCCTGGTAGTCC
The length of each sequence is 20. The blastn returns nident=17, with 3
mismatch.
However, T actually matches W and B, and G matches D.
With IUPAC characters, in this case, how can I also count ambiguous matches?
What I expect in this case is number of identity =20 instead of nident=17.
Is there any parameter for blastn so th... 阅读全帖 |
|
x**m
发帖数: 941 | 9 Full code:
proc sql;
create table seq as
select distinct a, b
from A
order by a, b;
run;
data seq2;
set seq;
by a b;
I+1;
if first.a then I=1;
run;
proc sql;
create table B as
select x.a, y.i
from A as x, seq2 as y
where x.a=y.a and x.b=y.b;
quit; |
|
b********e
发帖数: 693 | 10 下面的方法,可能稍微优化,但是不太想正确答案
1 .如果两个字符串size相同,那么先sort,然后比较, 如果相同,就是最大值, 否则
2 .在seq2里面, 找到第一个不在seq1里面的字符, 假设位置是X
那么最大值就在(0,x)和(x+1,n-1)这两个数组里面, 假设这两个字符串是A和B
如果所有字符都出现了, 那么这2个字符串是相等的
( |
|
c***2
发帖数: 838 | 11 Let’s first simplify the problem:
1) Assume the elements of both sequences contain only 26 upper case letters
(A..Z)
2) Assume both sequences don't have duplicate elements,
for example, "AABBC" is not allowed
With these in mind, it will be quite easy:
1) Map each sequence to a unsigned int32 (lower 26 bits)
seq1 = "ABCDEFG",
maps/hashes to b1= (000000) 00000000000000000001111111
seq2 = "DBCAPFG",
maps/hashes to b2=(000000) 00000000001000000001101111
2) c=b1&b2
3) Find the longest |
|
c*******w
发帖数: 63 | 12 假如:
Seq1: ABXCDEFG
Seq2: DBCAPFGX
Seq中的每个字母坐标:
4 1 3 0 (-1) 6 7 2
sort之后
0 1 3 4 -1 2 6 7
Window[A,B], Window[C,D]等都不是valid的candidate啊?
不知道我有没有正确理解AprilFlower的办法. |
|
c*******w
发帖数: 63 | 13 Counter Example:
Seq1: ABCDEFG
Seq2: ABXCDYZ
maps/hashes to b1= (000000) 00000000000000000001111111
maps/hashes to b2= (000000) 11100000000000000000001111
Is the answer: ABCD? It is not correct.
letters |
|
b********r
发帖数: 7725 | 14 没觉得，当然我在1/2里杀人不眨眼
基本都是裸奔到一堆士兵里面开始砍
从来没被砍死过
Seq2里有个地方，出来很多狼人
如果你不伤血杀光他们，会加sync值 |
|
l*******m
发帖数: 1096 | 15 如果数据量不大，定义个distance(seq1, seq2), 然后上kNN或SVM
比较流行的distance 是dynamic time wrapping （DTW）， DTW 是 O(n××2)的有些
慢，可以简化一下加速
x2 |
|
c*********r
发帖数: 1312 | 16 看到你这个话题，忍不住回复我所知道的一个人的例子。
这人叫Itai Yanai，以色列人。他本科在波士顿大学读Computer Engineering，应该是
1994年入学，在当时和现在都是很有前途的专业吧。Itai本科时候不老实，爱读闲书，
一不小心读了Richard Dawkins的The selfish gene，从此开始了悲催的一生。。。读
完这本自私的基因，Itai觉得生物是多么奇妙，就毅然决然的转行做生物了，Never
went back。在拿到computer engineering学士和Philosophy of Science学士以后，
Itai考虑到自己懂点计算机和编程，抛弃了作为一名伟大的编程员大好前程，在波士顿
大学读了生物信息学博士，度过了接下来的极其苦闷的五年。。。（他说那几年做生物
很不顺利，尤其是对于他这种没有任何生物背景的人。但是我看他PhD期间文章还有六
七篇，都是不错的杂志。）不管怎么样，他已经中毒很深，不可能回去了。。。
毕业之后，Itai在以色列和哈佛一共做了四年博后，然后在2008年回到了以色列做了PI
。那时候他已经开始从纯生物信息结合发... 阅读全帖 |
|
c*********r
发帖数: 1312 | 17 生物是个大坑，已经被讨论了好久了。因为和生物沾边， 生物信息也是一个坑，也被
讨论了一段时间了。但是总有人不听劝告，不断跳进来，今天我就写一个悲催的生物猥
琐男的故事，告诫后人。。。
Itai Yanai，以色列人。他本科在波士顿大学读Computer Engineering，应该是1994年
入学，在当时和现在都是很有前途的专业吧。Itai本科时候不老实，爱读闲书，一不小
心读了Richard Dawkins的The selfish gene，从此开始了悲催的一生。。。读完这本
自私的基因，Itai觉得生物是多么奇妙，就毅然决然的转行做生物了，Never went
back。在拿到computer engineering学士和Philosophy of Science学士以后，Itai考
虑到自己懂点计算机和编程，放弃了作为一名伟大的编程员大好前程，在波士顿大学读
了生物信息学博士，度过了接下来的极其苦闷的五年。。。（他说那几年做生物很不顺
利，尤其是对于他这种没有任何生物背景的人。但是我看他PhD期间文章还有六七篇，
都是不错的杂志。）不管怎么样，他已经中毒很深，不可能回去了。。。... 阅读全帖 |
|
J*X
发帖数: 1001 | 18 发信人: cellcreator (cellcreator), 信区: Biology
标 题: 一个从CS跳入生物信息大坑的猥琐男。
发信站: BBS 未名空间站 (Sun Mar 20 04:10:05 2016, 美东)
生物是个大坑，已经被讨论了好久了。因为和生物沾边， 生物信息也是一个坑，也被
讨论了一段时间了。但是总有人不听劝告，不断跳进来，今天我就写一个悲催的生物猥
琐男的故事，告诫后人。。。
Itai Yanai，以色列人。他本科在波士顿大学读Computer Engineering，应该是1993年
入学，在当时和现在都是很有前途的专业吧。Itai本科时候不老实，爱读闲书，一不小
心读了Richard Dawkins的The selfish gene，从此开始了悲催的一生。。。读完这本
自私的基因，Itai觉得生物是多么奇妙，就毅然决然的转行做生物了，Never went
back。在拿到computer engineering学士和Philosophy of Science学士以后，Itai考
虑到自己懂点计算机和编程，放弃了作为一名伟大的编程员大好前程，在波士顿... 阅读全帖 |
|
