改bioinformatic 求建议 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

改bioinformatic 求建议

改bioinformatic 求建议# Biology - 生物学

h*n2013-02-04 08:02

1 楼

很常见的一道题，
N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
大的数为第二大的数。我的问题是怎么写代码？谢谢！

p*y2013-02-04 08:02

2 楼

我记得看见有人说把CNKI的检索结果用google translate翻译一下，请问具体怎么操作
？多谢。答案正确有包子

t*g2013-02-04 08:02

3 楼

就是说可以申请F1么
读完书以后再申请h1b，申请绿卡会有问题么？

e*72013-02-04 08:02

4 楼

兄弟目前在生物实验室，想学bioinformatic，之前是血化工的，不过最近几年也没用
，都忘没了，倒是生物最近学到不少东西，经老板建议说学点bioinformatic不错，一
点基础没有啊，大家给点建议啊，计算机方面怎么开始啊，学什么课程，哪弄教材什么
的呢？
拜佛求，多谢万能空间

n*s2013-02-04 08:02

5 楼

类似于quick sort?

间。

【在 h***n 的大作中提到】

: 很常见的一道题，
: N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
: 算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
: 大的数为第二大的数。我的问题是怎么写代码？谢谢！

p*y2013-02-04 08:02

6 楼

自己找到了，没包子了

x*u2013-02-04 08:02

7 楼

I-140 shows immigration intent which F1 does not allow. You can try but it
is probably going to be hard...

e*u2013-02-04 08:02

8 楼

你要是为了找工作的话，赶紧读个cs master吧，为了research就另说

h*n2013-02-04 08:02

9 楼

算法是先要找最大数，然后利用其中的信息找到第二大数，quicksort中的partition没
有这层含义把
我只是想知道怎么用O(1)的空间实现n+log(n)-2的复杂度，因为好像没有人讨论

【在 n*s 的大作中提到】

: 类似于quick sort?
:
: 间。

r*l2013-02-04 08:02

10 楼

cnki自己就有英文版，不用翻译。

t*g2013-02-04 08:02

11 楼

说错了，是交了PERM还没有交140，这个有影响么？

e*o2013-02-04 08:02

12 楼

http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fjour
Introduction to Computer Science and Programming
Introduction to Databases
Building Dynamic Websites

i*e2013-02-04 08:02

13 楼

类似二分.
Hint: tournament match.
Below has a great description of this method.
Maybe the code can be simplified more using recursion.
http://www.seeingwithc.org/topic3html.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

a*n2013-02-04 08:02

14 楼

我好像听说交了perm，没交140不算有移民倾向，不过你还是问问学校里oiss 或者律师吧

【在 t**********g 的大作中提到】

: 说错了，是交了PERM还没有交140，这个有影响么？

e*o2013-02-04 08:02

15 楼

我以前写的：
http://www.mitbbs.com/article0/Biology/31733509_0.html
我自己也在往bioinfo上转，仅供参考。

h*d2013-02-04 08:02

16 楼

用两个variable分别存最大数和第二大数
你说两两比较找最大数的同时，顺便用第二个variable update第二大数
是这样吗？

间。

【在 h***n 的大作中提到】

c*e2013-02-04 08:02

17 楼

不影响

【在 t**********g 的大作中提到】

: 说错了，是交了PERM还没有交140，这个有影响么？

e*o2013-02-04 08:02

18 楼

图书馆书都有基本。
想看电子版， google 书名 + ishare 。

S*I2013-02-04 08:02

19 楼

就是用quick sort里的partition来实现；C++ STL algorithm里的nth_element和
partial_sort就是干这个的，具体实现见：
http://blogs.msdn.com/b/devdev/archive/2006/01/18/514482.aspx

【在 h***n 的大作中提到】

: 算法是先要找最大数，然后利用其中的信息找到第二大数，quicksort中的partition没
: 有这层含义把
: 我只是想知道怎么用O(1)的空间实现n+log(n)-2的复杂度，因为好像没有人讨论

u*12013-02-04 08:02

20 楼

Don't read those lengthy bioinformatics book.Simply a waste of time.
Directly go for a project;
Whenever you have problem, simply google; you'll find answers from such
bioinfor forums as Biostar or sequanswer.
For pure coding problem, raise questions in stackoverflow.
Unless you have a very strong mathmatical background and aim to be
specialized in methodology, mostly your project is to solve biological
problems using available approaches.
Very first, learn some most basic shell commands/get familiar with Linux
system.
【在 eric6767 (eric6767) 的大作中提到: 】

l*f2013-02-04 08:02

21 楼

Heap sort N-1, 然后 reheap一下搞定

e*72013-02-04 08:02

22 楼

多谢楼上几位弟兄的建议啊，目前在工作，倒是有个小project在学呢，不过要被老板
逼疯了啊，希望尽快有收获，然后恶补计算机知识，请问一个问题，这linux系统是个
必须学的吗？要是是的话我就把windows删了，天天用这个，熟了为止，多谢达人啊

i*92013-02-04 08:02

23 楼

i don't think this can be done without using extra memory.

间。

【在 h***n 的大作中提到】

e*o2013-02-04 08:02

24 楼

必须。
可以转个虚拟机或者双系统。
完全安装也可以，不过有些学校联网是个问题，要自己折腾。
可以找个linux的书翻翻。

【在 e******7 的大作中提到】

: 多谢楼上几位弟兄的建议啊，目前在工作，倒是有个小project在学呢，不过要被老板
: 逼疯了啊，希望尽快有收获，然后恶补计算机知识，请问一个问题，这linux系统是个
: 必须学的吗？要是是的话我就把windows删了，天天用这个，熟了为止，多谢达人啊

c*t2013-02-04 08:02

25 楼

这个好。实现了n+lg(n)-2的time. 可是lz说不需要额外空间啊？
不管是你的方法还是quick sort，都必须要额外的空间吧？

【在 i**********e 的大作中提到】

: 类似二分.
: Hint: tournament match.
: Below has a great description of this method.
: Maybe the code can be simplified more using recursion.
: http://www.seeingwithc.org/topic3html.html
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

l*12013-02-04 08:02

26 楼

Sure LZ can try VCN under SSH UNIX server if LZ your boss/mentor permitted
or just pay USD for buying UNIX server access account from your
college/university/institure IT department etc.
Reference:
HTTP: //www.cl.cam.ac.uk/research/dtg/attarchive/vnc/sshwin.html

c*t2013-02-04 08:02

27 楼

不行，你这样复杂度是 2n-3

【在 h**********d 的大作中提到】

: 用两个variable分别存最大数和第二大数
: 你说两两比较找最大数的同时，顺便用第二个variable update第二大数
: 是这样吗？
:
: 间。

c*l2013-02-04 08:02

28 楼

Learn a script language, such as perl and python.

【在 e******7 的大作中提到】

: 兄弟目前在生物实验室，想学bioinformatic，之前是血化工的，不过最近几年也没用
: ，都忘没了，倒是生物最近学到不少东西，经老板建议说学点bioinformatic不错，一
: 点基础没有啊，大家给点建议啊，计算机方面怎么开始啊，学什么课程，哪弄教材什么
: 的呢？
: 拜佛求，多谢万能空间

c*t2013-02-04 08:02

29 楼

好像是不可能。要么要存比较过哪些数，要么要存原始的index位置(swap)。我想了想
，没想通，抛砖引玉,说说我的想法吧。
O(1) space. 就是可以有variable. 如果只用swap，就可以做到要求。
比如ihasleetcode的方法，如果能不用空间保存和最大数比较过的数就可以实现。我延
伸一下，两两比较如果swap大的数到前面。那么得出最大数(第一个数）的同时，如果
知道了它原始的index。从这个index应该有方法知道，都比较过哪些数，比如第2个数
最大，那么最后就应该和 2，3，5，9，17... 2^i+1... 比较过。第11个数最大，最后
就应该和9，11，12，17，...2^i+1比较过。这些比较过数里的最大的就是second max.
所以是lg(n)-1
可是我的难题是第一，没有储存原始index。第二，虽然有规律，但还不知道如何算哪
些index比较过。
用quick sort + swap 也类似，好像知道最大数比较过的patition最左边数再比较就可
以知道second。

【在 i**9 的大作中提到】

: i don't think this can be done without using extra memory.
:
: 间。

a*h2013-02-04 08:02

30 楼

强烈赞同。
linux, shell script 重要好学，而且上手快。
如果有多的时间，再去学一门语言，比如perl,c,java,python 看你自己的时间和入门
速度以及和project相关程度。
做project最重要。

【在 u*********1 的大作中提到】

: Don't read those lengthy bioinformatics book.Simply a waste of time.
: Directly go for a project;
: Whenever you have problem, simply google; you'll find answers from such
: bioinfor forums as Biostar or sequanswer.
: For pure coding problem, raise questions in stackoverflow.
: Unless you have a very strong mathmatical background and aim to be
: specialized in methodology, mostly your project is to solve biological
: problems using available approaches.
: Very first, learn some most basic shell commands/get familiar with Linux
: system.

j*p2013-02-04 08:02

31 楼

同意楼上的

C*e2013-02-04 08:02

32 楼

去学python吧
现在大势所趋
而且很多生物相关的module都有
可以拿来用

y*i2013-02-04 08:02

33 楼

问个菜鸟问题，为什么非学Unix Linux？在做什么工作特别重要，甚至不可缺少？

【在 u*********1 的大作中提到】

a*h2013-02-04 08:02

34 楼

因为数据分析都在这个平台上。很多软件也是只在Unix/Linux。

【在 y***i 的大作中提到】

: 问个菜鸟问题，为什么非学Unix Linux？在做什么工作特别重要，甚至不可缺少？

d*r2013-02-04 08:02

35 楼

All the industrial computation systems are Unix and/or Linux.

【在 y***i 的大作中提到】

: 问个菜鸟问题，为什么非学Unix Linux？在做什么工作特别重要，甚至不可缺少？

l*12013-02-04 08:02

36 楼

生物信息学的话考古下本分舵的旧贴:
http://www.mitbbs.com/article_t/Biology/31778379.html
生物统计学生物数学人工/合成/系统生物学的论文投稿
里边的公式或行列式必用TeX/LaTeX模板
而哥各文本 run 成 dvi pdf 时
必用 Unix/Linux shell command script (perl or others)
one sample pls refer
Elsevier manuscript used:
HTTP: //www.math.zju.edu.cn/ligangliu/LatexForum/tex_template.htm
more references pls go to:
HTTP: //www.math.zju.edu.cn/ligangliu/LatexForum/tex_link.htm

【在 y***i 的大作中提到】

: 问个菜鸟问题，为什么非学Unix Linux？在做什么工作特别重要，甚至不可缺少？

e*72013-02-04 08:02

37 楼

看了大家的帖子，真是太好了，多谢各位大侠啊。

l*12013-02-04 08:02

38 楼

不谢
btw, matrix 虾米一个千万别叫大虾吧

【在 e******7 的大作中提到】

: 看了大家的帖子，真是太好了，多谢各位大侠啊。

e*e2013-02-04 08:02

39 楼

tks

e*o2013-02-04 08:02

40 楼

这次失误了。
请搜素 MiKTex

【在 l**********1 的大作中提到】

: 生物信息学的话考古下本分舵的旧贴:
: http://www.mitbbs.com/article_t/Biology/31778379.html
: 生物统计学生物数学人工/合成/系统生物学的论文投稿
: 里边的公式或行列式必用TeX/LaTeX模板
: 而哥各文本 run 成 dvi pdf 时
: 必用 Unix/Linux shell command script (perl or others)
: one sample pls refer
: Elsevier manuscript used:
: HTTP: //www.math.zju.edu.cn/ligangliu/LatexForum/tex_template.htm
: more references pls go to:

l*12013-02-04 08:02

41 楼

sure you are using WIN7 or 8 WINXP PC with MT
but matrix almostly use Unix/Linux/Mac OS
ps:
about MT
also pls refer,
HTTP: //www.math.nus.edu.sg/aslaksen/
and plus
考古下mitbbs Bio sub branch one 旧贴:
Biology版 - 从投稿到发表一共14年！看看这个math作者得有多强的心理素质
HTTP: //www.weiming.info/zhuti/Biology/31637395/
or
HTTP: //blog.sciencenet.cn/blog-579446-654476.html
that 14 Ys paper first author is above MT noted web site: Aslaksen H
that paper its title:
Generators of matrix algebras in dimension 2 and 3, Linear Algebra and its
Applications. 430 (2009)
web link:
HTTP: //www.math.nus.edu.sg/aslaksen/helmerpub.html

【在 e*******o 的大作中提到】

: 这次失误了。
: 请搜素 MiKTex