The Bioinformatics Group
Department of Computer Science
Rice University

1. Jeff Arenson.
2. Melanie Beyt.
3. Riya Fukui.
4. Skyler Johnson.
5. Alen Lukic.
6. Rick Manning.
7. Travis Martin.
8. Aubrey Sirtautas.
9. Rick Song.
10. Lindsey Wohlfort (UT Austin undergrad).

Students' Awards

• Jeff Kilpatrick: The DOE/Krell graduate fellowship, winner.
• Derek Ruths: The NSF graduate fellowship, honorable mention.
• Troy Ruths: The NSF graduate fellowship, winner.
• Troy Ruths: The DOE/Krell graduate fellowship, winner.
• Troy Ruths: The Hertz Foundation fellowship, finalist.
• Cuong Than: The Vietnamese Education Foundation (VEF) fellowship.

Projects

• Methodologies for reconstructing and analyzing phylogenetic networks.
• Methodologies for inferring species trees despite lineage sorting.
• Methodologies for distinguishing among the various gene tree discord factors, such as lineage sorting, horizontal gene transfer (HGT), and gene duplication/loss.
• Analysis of microbial genomes and quantification of recombination and HGT rates.
• Constructing executable models of regulatory networks, and elucidating their role in cancer.
• Methodologies for detecting multi-locus genotype-phenotype association.
• Elucidating the mechanisms behind the evolution of genetic networks, and reconstructing their evolution.
• Structural and dynamic modeling of metabolic networks, mainly in bacteria.

Publications

62	N. Berestovsky*, R. Fukui*, and L. Nakhleh, "On the performance of particle swarm optimization for parameterizing kinetic models of cellular networks." Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology. To appear, 2012.
61	S. Takuno, T. Kado, R.P. Sugino, L. Nakhleh, and H. Innan, "Population genomics in bacteria: A case study of Staphylococcus aureus." Molecular Biology and Evolution, 29(2): 797-809, 2012. (Supplementary Material)
60	Y. Yu*, T. Warnow, and L. Nakhleh, "Algorithms for MDC-based multi-locus phylogeny inference: Beyond rooted binary gene trees on single alleles." Journal of Computational Biology, 18(11): 1543-1559, 2011.
59	W. Zhou* and L. Nakhleh, "The strength of chemical linkage as a criterion for pruning metabolic graphs." Bioinformatics, 27(14): 1957-1963, 2011. (Supplementary Material)
58	Y. Lu, M. Muller, D. Smith, B. Dutta, K. Komurov, S. Iadevaia, D. Ruths*, J-T. Tseng, S. Yu, Q. Yu, L. Nakhleh, G. Balazsi, J. Donnelly, M. Schurdak, S. Morgan-Lappe, S. Fesik, P.T. Ram, and G.B. Mills, "Kinome siRNA-phosphoproteomic screen identifies networks regulating AKT signaling." Oncogene, 30(45): 4567-4577, 2011. (Supplementary Material)
57	W. Zhou* and L. Nakhleh, "Properties of metabolic graphs: Biological organization or representation artifacts?" BMC Bioinformatics, 12: 132, 2011.
56	Y. Yu*, T. Warnow, and L. Nakhleh, "Algorithms for MDC-based multi-locus phylogeny inference." Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB), LNBI 6577, 531-545, 2011. [Typo: third line in Theorem 5 should read "..that is NOT in A."]
55	Y. Yu*, C. Than*, J.H. Degnan, and L. Nakhleh, "Coalescent histories on phylogenetic networks and detection of hybridization despite incomplete lineage sorting." Systematic Biology, 60(2):138-149, 2011.
54	H.J. Park*, G. Jin, and L. Nakhleh, "Algorithmic strategies for estimating the amount of reticulation from a collection of gene trees." Proceedings of the 9th Annual International Conference on Computational Systems Biology, 114-123, 2010.
53	D. Ruths* and L. Nakhleh, "Deriving predictive models of signaling network dynamics from qualitative experimental data." Proceedings of the 9th Annual International Conference on Computational Systems Biology, 136-145, 2010.
52	C. Than* and L. Nakhleh, "Inference of parsimonious species phylogenies from multi-locus data by minimizing deep coalescences." In: Estimating Species Trees: Practical and Theoretical Aspects, L.L. Knowles and L.S. Kubatko (eds.), Wiley-VCH, 79-98, 2010.
51	L. Nakhleh, "Evolutionary phylogenetic networks: models and issues." In: The Problem Solving Handbook for Computational Biology and Bioinformatics, L. Heath and N. Ramakrishnan (editors). Springer, 125-158, 2010.
50	H.J. Park*, G. Jin, and L. Nakhleh, "Bootstrap-based support of HGT inferred by maximum parsimony." BMC Evolutionary Biology, 10: 131, 2010.
49	L. Nakhleh, "A Metric on the Space of Reduced Phylogenetic Networks." IEEE/ACM Transactions on Computational Biology and Bioinformatics, 7(2): 218-222, 2010.
48	C. Than* and L. Nakhleh, "Species tree inference by minimizing deep coalescences." PLoS Computational Biology, 5(9): e1000501, 2009.
47	L. Nakhleh, D. Ruths*, and H. Innan, "Gene Trees, Species Trees, and Species Networks." In: Meta-analysis and Combining Information in Genetics, R. Guerra and D. Goldstein (editors). CRC Press, 275-293, 2009.
46	T. Ruths*, D. Ruths*, and L. Nakhleh, "GS2: An efficiently computable measure of GO-based similarity of gene sets." Bioinformatics, 25(9): 1178-1184, 2009.
45	F. Barbancon, T. Warnow, D. Ringe, S. Evans, and L. Nakhleh, "An experimental study comparing linguistic phylogenetic reconstruction methods." Proceedings of the conference Languages and Genes, held at UC Santa Barbara (Cambridge University Press). To appear, 2009.
44	G. Jin, L. Nakhleh, S. Snir, and T. Tuller, "Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-time Heuristic." IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(3): 495-505, 2009.
43	C. Than&Dagger, G. Jin, and L. Nakhleh, "Integrating Sequence and Topology for Efficient and Accurate Detection of Horizontal Gene Transfer." Proceedings of the Sixth RECOMB Comparative Genomics Satellite Workshop. Lecture Notes in Bioinformatics (LNBI #5267), 113-127, 2008.
42	C. Than&Dagger, D. Ruths&Dagger, and L. Nakhleh, "PhyloNet: A Software Package for Analyzing and Reconstructing Reticulate Evolutionary Relationships." BMC Bioinformatics, 9:322, 2008.
41	D. Ruths&Dagger, L. Nakhleh, and P.T. Ram, "Rapidly Exploring Structural and Dynamic Properties of Signaling Networks Using PathwayOracle." BMC Systems Biology, 2:76, 2008.
40	I. Kanj, L. Nakhleh, C. Than&Dagger, and G. Xia, "Seeing the Trees and Their Branches in the Network is Hard." Theoretical Computer Science (TCS), 401: 153-164, 2008.
39	C. Than&Dagger, R. Sugino, H. Innan, and L. Nakhleh, "Efficient Inference of Bacterial Strain Trees From Genome-scale Multi-locus Data." The 16th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB). Bioinformatics, 24: i123-i131, 2008.
38	D. Ruths&Dagger, M. Muller, J.T. Tseng, L. Nakhleh, and P.T. Ram, "The Signaling Petri Net-based Simulator: A Non-parametric Strategy for Characterizing the Dynamics of Cell-specific Signaling Networks." PLoS Computational Biology, 4(2): e1000005, 2008.
37	I. Kanj, L. Nakhleh, and G. Xia, "The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms." Algorithmica, 51: 99-128, 2008.
36	C. Than&Dagger and L. Nakhleh, "SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions." Proceedings of the Sixth Asia Pacific Bioinformatics Conference (APBC), 251-260, 2008.
35	I. Kanj, L. Nakhleh, C. Than&Dagger, and G. Xia, "Seeing the Trees and Their Branches in the Network is Hard." Proceedings of the Tenth Italian Conference on Theoretical Computer Science (ICTCS), 82-93, 2007.
34	C. Than&Dagger, D. Ruths&Dagger, H. Innan, and L. Nakhleh, "Confounding Factors in HGT Detection: Statistical Error, Coalescent Effects, and Multiple Solutions." Journal of Computational Biology, 14(4): 517-535, 2007. (Typo: In Condition 2 of Definition 2, the "if" statement should read: "if e1 is below e2, then h(alpha(e1)) <= h(alpha(e2))".)
33	G. Jin, L. Nakhleh, S. Snir, and T. Tuller, "A New Linear-time Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance." Proceedings of the International Symposium on Bioinformatics Research and Applications (ISBRA). Lecture Notes in Bioinformatics (LNBI #4463), 61-72, 2007.
32	D. Ruths&Dagger, J.T. Tseng, L. Nakhleh, and P.T. Ram, "De novo Signaling Pathway Predictions based on Protein-Protein Interaction, Targeted Therapy and Protein Microarray Analysis." Proceedings of the RECOMB Satellite Workshop on Systems Biology and Proteomics. Lecture Notes in Bioinformatics (LNBI #4205), 108-118, 2007.
31	G. Jin, L. Nakhleh, S. Snir, and T. Tuller, "Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study." Molecular Biology and Evolution, 24(1): 324-337, 2007.
30	G. Jin, L. Nakhleh, S. Snir, and T. Tuller, "Maximum Likelihood of Phylogenetic Networks." Bioinformatics, 22(21): 2604-2611, 2006. (The supplementary material contains the proofs and more technical details.)
29	C. Than&Dagger, D. Ruths&Dagger, H. Innan, and L. Nakhleh, "Identifiability Issues in Phylogeny-based Detection of Horizontal Gene Transfer." Proceedings of the Fourth RECOMB Comparative Genomics Satellite Workshop. Lecture Notes in Bioinformatics (LNBI 4205), 215-229, 2006. [Typo in formula (1) on page 223: the summation should be a product.]
28	D. Ruths&Dagger, L. Nakhleh, M.S. Iyengar, S.A.G. Reddy, and P.T. Ram, "Graph-theoretic Hypothesis Generation in Biological Signaling Networks." Journal of Computational Biology, 13(9): 1546-1557, 2006.
27	G. Jin, L. Nakhleh, S. Snir, and T. Tuller, "Efficient Parsimony-based Methods for Phylogenetic Network Reconstruction." Bioinformatics, 23:e123-e128, 2006. (Proceedings of the European Conference on Computational Biology (ECCB 2006)).
26	T. Shigaki, I. Rees, L. Nakhleh, and K. Hirschi, "Identification of Three Distinct Phylogenetic Groups of CAX Cation/Proton Antiporters." Journal of Molecular Evolution, 63:815-825, 2006.
25	I. Kanj, L. Nakhleh, and G. Xia, "Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms." Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON 2006). Lecture Notes in Computer Science (LNCS #4112), 299-308, 2006.
24	Y. Dotsenko, C. Coarfa, L. Nakhleh, J. Mellor-Crummey, and U. Roshan, "PRec-I-DCM3: A Parallel Framework for Fast and Accurate Large Scale Phylogeny Reconstruction." International Journal on Bioinformatics Research and Applications (IJBRA), 2(4): 407-419, 2006.
23	D. Ruths&Dagger and L. Nakhleh, "Techniques for Assessing Phylogenetic Branch Support: A Performance Study." Proceedings of the Forth Asia-Pacific Bioinformatics Conference, (APBC2006), 187-196, 2006.
22	D. Ruths&Dagger and L. Nakhleh, "RECOMP: A Parsimony-based Method for Detecting Recombination." Proceedings of the Forth Asia-Pacific Bioinformatics Conference, (APBC2006), 59-68, 2006.
21	Z. Du, A. Stamatakis, F. Lin, U. Roshan, and L. Nakhleh, "Parallel divide-and-conquer phylogeny reconstruction by maximum likelihood." Proceedings of the 2005 International Conference on High Performance Computing and Communications (HPCC 05), 2:346-350, 2005.
20	L. Nakhleh, G. Jin, F. Zhao, and J. Mellor-Crummey, "Reconstructing Phylogenetic Networks Using Maximum Parsimony." Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference (CSB2005), 93-102, 2005.
19	L. Nakhleh and L.S. Wang, "Phylogenetic Networks: Properties and Relationship to Trees and Clusters." LNCS Transactions on Computational Systems Biology, II, LNBI 3680, 82-99, 2005.
18	L. Nakhleh, D. Ruths&Dagger, and L.S. Wang, "RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer." Proceedings of the Eleventh International Computing and Combinatorics Conference (COCOON 05). LNCS #3595 (L. Wang, editor), 84-93, 2005.
17	C. Coarfa, Y. Dotsenko, J. Mellor-Crummey, L. Nakhleh, and U. Roshan, "PRec-I-DCM3: A Parallel Framework for Fast and Accurate Large Scale Phylogeny Reconstruction." Proceedigns of the First IEEE Workshop on High Performance Computing in Medicine and Biology (HiPCoMP 2005), 2:346-350, 2005. (Best paper award.)
16	D. Ruths&Dagger and L. Nakhleh, "Recombination and Phylogeny: Effects and Detection." The International Journal of Bioinformatics Research and Applications (IJBRA), 1(2): 202-212, 2005.
15	L. Nakhleh, T. Warnow, D. Ringe, and S.N. Evans, "A Comparison of Phylogenetic Reconstruction Methods on an IE Dataset." Transactions of the Philological Society, 3(2): 171-192, 2005.
14	L. Nakhleh and L.S. Wang, "Phylogenetic Networks, Trees, and Clusters." Proceedings of the 2005 International Workshop on Bioinformatics Research and Applications (IWBRA 05). Lecture Notes in Computer Science, LNCS #3515, pp. 919-926, 2005.
13	L. Nakhleh, T. Warnow, C.R. Linder, and K. St. John, "Reconstructing Reticulate Evolution in Species -- Theory and Practice." Journal of Computational Biology, 12(6-7), 796-811, 2005.
12	L. Nakhleh, D. Ringe, and T. Warnow, "Perfect Phylogenetic Networks: A New Methodology for Reconstructing the Evolutionary History of Natural Languages." LANGUAGE, Journal of the Linguistic Society of America. 81(2):382-420, 2005.
11	B.M.E. Moret, L. Nakhleh, T. Warnow, C.R. Linder, A. Tholse, A. Padolina, J. Sun, and R. Timme, "Phylogenetic networks: modeling, reconstructibility, and accuracy." The IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1(1):13-23, 2004. [Lemma 1 is incorrect (and, consequently, Theorem 3 is incorrect). m^{tri} is a dissimilarity measure, but not a metric on the space of reduced networks. Further, the reduction procedure does not accurately capture the "indistinguishability" part. See Publication #46 above for a metric on the space of reduced phylogenetic networks, and for a revised version of the reduction procedure.]
10	T. Warnow, S.N. Evans, D. Ringe, and L. Nakhleh, "A Stochastic model of language evolution that incorporates homoplasy and borrowing." Phylogenetic Methods and the Prehistory of Languages. Cambridge, UK, July 2004.
9	L. Nakhleh, T. Warnow, and C.R. Linder, "Reconstructing Reticulate Evolution in Species -- Theory and Practice." Proceedings of the Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2004), 337-346.
8	C.R. Linder, B.M.E. Moret, L. Nakhleh, and T. Warnow, "Network (Reticulate) Evolution: Biology, Models, and Algorithms." A tutorial presented at The Ninth Pacific Symposium on Biocomputing (PSB 2004).
7	L. Nakhleh, D. Miranker, F. Barbancon, W.H. Piel, and M.J. Donoghue, "Requirements of Phylogenetic Databases." Proceedings of the Third IEEE Symposium on Bioinformatics and Bioengineering (BIBE 2003), IEEE Press, 2003, 141-148. (Full technical report version of the paper: PDF.)
6	E. Erdem, V. Lifschitz, L. Nakhleh, and D. Ringe, "Reconstructing the Evolutionary History of Indo-European Languages using Answer Set Programming." Proceedings of the Fifth International Symposium on Practical Aspects of Declarative Languages (PADL 2003). Lecture Notes in Computer Science (LNCS #2562).
5	L. Nakhleh, J. Sun, T. Warnow, C.R. Linder, B.M.E. Moret, and Anna Tholse, "Towards the Development of Computational Tools for Evaluating Phylogenetic Network Reconstruction Methods." Proceedings of the Eighth Pacific Symposium on Biocomputing (PSB 03), January 2003.
4	L. Nakhleh, U. Roshan, L. Vawter, and T. Warnow, "Estimating the Deviation from a Molecular Clock." Proceedings of the Second International Workshop on Algorithms in Bioinformatics (WABI 02), Rome, Italy, Lecture Notes in Computer Science (LNCS #2452).
3	L. Nakhleh, B.M.E. Moret, U. Roshan, K. St. John, J. Sun, and T. Warnow, "The Accuracy of Phylogenetic Methods for Large Datasets." Proceedings of the Seventh Pacific Symposium on Biocomputing (PSB 02), 7:211-222, January 2002.
2	L. Nakhleh, U. Roshan, K. St. John, J. Sun, and T. Warnow, "The Performance of Phylogenetic Methods on Trees of Bounded Diameter." Proceedings of the First International Workshop on Algorithms in Bioinformatics (WABI 01), Aarhus, Denmark, Lecture Notes in Computer Science (LNCS #2149). Pages 214-226.
1	L. Nakhleh, U. Roshan, K. St. John, J. Sun, and T. Warnow, "Designing Fast Converging Phylogenetic Methods." Bioinformatics, 17(90001), pp S190-S198, 2001. Proceedings of the Ninth International Conference on Intelligent Systems for Molecular Biology (ISMB 01), Copenhagen, Denmark.

Software

• PhyloNet: A suite of software tools for reconstructing/analyzing phylogenetic networks in the presence of reticulate evolutionary events, as well as inferring species trees despite lineage sorting.
• TS2B: A tool for learning Boolean networks from time-series data.
• NEPAL: A suite of software tools for reconstructing and analyzing phylogenetic networks under the maximum parsimony (MP) and maximum likelihood (ML) optimization criteria.
• PathwayOracle: A suite of software tools for topology-based analyses of signal transduction networks.
• GS²: A tool for computing the Gene Ontology (GO) based similarity of a set of genes.
• Network Evolution: tools for distance correction and ancestral reconstruction for evolutionary analysis of molecular interaction networks.
• Community Detection: tools for community detection in metabolic networks (and networks in general).
• AGR: A tool that implements the Association Graph Reduction technique for detecting multi-locus genotype-phenotype association.
• SimGE: A tool for simulating case/control data sets with various models of interacting markers.

Support

• National Science Foundation: "ABI Innovation: Collaborative Research: Novel methodologies for genome-scale evolutionary analysis of multi-locus data."
• The Gulf Coast Center for Computational Cancer Research (GC4R): "Network-guided integration of omics data for predicting therapeutic combinations."
• National Science Foundation: "CAREER: Computational tools for evolutionary analysis of biological networks."
• National Science Foundation: "SGER: NET HMMs and their applications to biological network alignment."
• NIH National Library of Medicine: "Evolutionary analysis of bacterial genomes -- High-throughput computational tools."
• NIH National Cancer Institute: "Determinants of signaling network regulation in combinatorial targeted therapies."
• The Gulf Coast Center for Computational Cancer Research (GC4R): "Using signaling networks and proteomic data for computational prediction of therapeutic targets."
• The George R. Brown School of Engineering, Rice University: The Roy E. Campbell Faculty Development Award.
• Department of Energy: "Tools for accurate and efficient analysis of complex evolutionary mechanisms in microbial genomes."
• National Science Foundation: "Efficient techniques for reconstructing horizontal gene transfer in bacteria."
• The Department of Computer Science, Rice University: Start-up package.

Contact