1. INTRODUCTIONThe consensus tree p

1. INTRODUCTION
The consensus tree problem has been rst described in [1]
alongside with a solution method. It frequently appears in
the domain of phylogenetics [13], though it has applications
in other clustering domains as well.
A phylogenetic tree is composed of nodes and branches
(arcs) and models the evolutionary relationship between a
set L of related objects called taxa. These taxa are the labeled
leaf nodes of the tree whereas unlabeled inner nodes
represent probably extinct ancestors. In this work we will
only consider rooted unweighted binary trees, i.e. there exists
a single distinguished root node being the common ancestor
of all taxa, the relations represented by the tree are
not weighted by any means, and each inner node always has
exactly two direct descendants.
The phylogeny problem is to infer the intermediate ancestors
and branches, thus to derive the evolutionary relationships,
from given species data like DNA or RNA sequences.
For this purpose a multitude of conceptually dierent inference
methods exists, each having individual advantages and
drawbacks [15].
Unfortunately, it is likely that biologists end up with several
dierent trees for one and the same taxa set L due to
(i) having multiple data sets available, (ii) inferring with
dierent methods, or (iii) repeated runs of the same nondeterministic
method.
The question is then how to take advantage of these probably
high-quality but dierent and partly contradictory trees
beside manually comparing and merging them. A possible
solution is to look for a single tree over L est" representing
the collection T . This non-trivial task is known as the
consensus tree problem (CTP).
On the one hand the meaning of est" depends on the desired
information to retain in the consensus tree and on the
other hand the possible consensus tree is literally restricted
by the degree of strictness of the applied method as well as
the granularity of the tree metric used, see also [3]. Figure 1
shows a schematic representation of this circumstance. Generally,
a strict method and a coarse-grained metric rather
lead to poorly resolved trees with few inner nodes having
high degrees, and a substantial portion of the information
contained in the input trees is lost. In contrast, we aim at
deriving fully resolved (thus, binary) high-quality consensus
trees inheriting as much information as possible. Our
approach is therefore based on maximizing a more specic
ne-grained measure, the so-called TreeRank score.
In Section 2 we report on previous as well as related work
and dene the TreeRank measure. Meaningful tree neigh-

ผลลัพธ์ (ไทย) 1:

1. บทนำปัญหาต้นไม้ช่วยได้ rst ที่อธิบายไว้ใน [1]ควบคู่ไปกับวิธีการแก้ปัญหา มันมักปรากฏในโดเมนของวงศ์วานวิวัฒนาการ [13], แม้ว่าจะมีโปรแกรมประยุกต์ในระบบคลัสเตอร์โดเมนอื่น ๆ เช่นต้นไม้ phylogenetic ประกอบด้วยโหนดและสาขา(เส้นโค้ง) และโมเดลความสัมพันธ์เชิงวิวัฒนาการระหว่างการตั้ง L วัตถุที่เกี่ยวข้องเรียก taxa Taxa เหล่านี้อยู่ที่ป้ายใบโหนดของต้นไม้ขณะเพียงภายในโหนหมายถึงบรรพบุรุษคงสูญ ในงานนี้ เราจะพิจารณาเฉพาะ ราก unweighted นารีต้นไม้ เช่นมีโหนดรากเดียวแตกต่างมีบรรพบุรุษร่วมกันtaxa ทั้งหมด ความสัมพันธ์ที่แสดง ด้วยแผนภูมิเป็นไม่ถ่วงน้ำหนัก โดยวิธีการใด ๆ และแต่ละโหนภายในจะมีสองลูกหลานโดยตรงปัญหา phylogeny จะเข้าใจบรรพบุรุษกลางสาขา และดังนั้นสามารถรับความสัมพันธ์เชิงวิวัฒนาการจากกำหนดชนิดข้อมูลเช่นลำดับดีเอ็นเอหรืออาร์เอ็นเอสำหรับวัตถุประสงค์นี้ได้หลากหลายทางแนวคิดข้อ erent ดิวิธีการมีอยู่ แต่ละที่มีข้อดีแต่ละ และข้อเสีย [15]อับ ก็มีแนวโน้มว่า biologists ลงท้ายด้วยต้นไม้ erent di taxa เดียวตั้ง L เนื่อง(i) มีชุดข้อมูลหลายว่าง, (ii) inferring ด้วยวิธี erent di หรือ (iii) ซ้ำทำเดียวกันถูกวิธีการคำถามคือแล้ว วิธีการใช้ประโยชน์จากเหล่านี้อาจคุณภาพดี erent และต้นไม้บางส่วนขัดแย้งนอกจากการเปรียบเทียบ และผสานไว้ด้วยตนเอง เป็นไปได้ทางออกคือการ หาต้นไม้เดียวผ่าน L est"แทนชุด T งานนี้ไม่ใช่เล็กน้อยเรียกว่าเป็นการช่วยให้แผนภูมิปัญหา (CTP)ในมือความหมายของ est"ขึ้นอยู่กับที่ต้องข้อมูลที่จะคง ไว้ ในแผนภูมิช่วยในการอีกต้นช่วยได้ถูกจำกัดอย่างแท้จริงโดยระดับของ strictness วิธีใช้ตลอดจนองค์ประกอบของการวัดแผนภูมิที่ใช้ ดู [3] รูปที่ 1แสดงการนำเสนอสถานการณ์นี้มัน ทั่วไปวิธีการเข้มงวดและการวัด coarse-grained แทนทำให้ต้นไม้ไม่ดีแก้ไขกับโหนภายในไม่กี่ที่มีองศาสูง และส่วนของข้อมูลที่พบในการป้อนข้อมูลต้นไม้เสียหาย ในทางตรงข้าม เรามุ่งมั่นที่บริษัทฯ ทั้งหมดได้รับการแก้ไข (ดัง ไบนารี) ช่วยให้มีคุณภาพสูงต้นไม้ที่สืบทอดข้อมูลมากที่สุด ของเราวิธีการจึงยึดเพิ่ม c เป็น speci เพิ่มเติม เม็ดมุวัด คะแนน TreeRank เรียกว่าในส่วน 2 ที่เรารายงานงานก่อนหน้า รวมทั้งที่เกี่ยวข้องและเดอมุวัด TreeRank เห็นต้นไม้ที่มีความหมาย-

ผลลัพธ์ (ไทย) 2:

1.
บทนำปัญหาต้นไม้ฉันทามติได้รับการอธิบายในครั้งแรก[1]
ข้างด้วยวิธีการแก้ปัญหา มันมักจะปรากฏอยู่ในโดเมนของ phylogenetics [13] แม้ว่ามันจะมีการใช้งานในโดเมนการจัดกลุ่มอื่นๆ เช่นกัน. ต้นไม้สายวิวัฒนาการประกอบด้วยโหนดและสาขา(โค้ง) และรูปแบบความสัมพันธ์ระหว่างวิวัฒนาการL ชุดของวัตถุที่เกี่ยวข้องที่เรียกว่าแท็กซ่า แท็กซ่าเหล่านี้เป็นที่มีข้อความโหนดใบของต้นไม้ในขณะที่โหนดภายในที่ไม่มีป้ายกำกับเป็นตัวแทนของบรรพบุรุษอาจจะสูญพันธุ์ ในงานนี้เราจะพิจารณาเฉพาะที่ฝังรากต้นไม้ไบนารีชั่งคือมีอยู่โหนดรากที่แตกต่างเดียวที่เป็นบรรพบุรุษร่วมกันของแท็กซ่าทั้งหมด, ความสัมพันธ์ที่แสดงโดยต้นไม้จะไม่ได้ถ่วงน้ำหนักด้วยวิธีการใด ๆ และแต่ละโหนดภายในมักจะมีตรงสองโดยตรงลูกหลาน. ปัญหาเชื้อชาติคือการสรุปบรรพบุรุษกลางและสาขาจึงจะได้รับความสัมพันธ์ที่วิวัฒนาการจากข้อมูลสายพันธุ์ที่ได้รับเช่นดีเอ็นเอหรืออาร์เอ็นเอ. ในการนี้ความหลากหลายของแนวคิดดิ? ต่างกันข้อสรุปวิธีการที่มีอยู่แต่ละคนมีข้อดีของแต่ละบุคคลและข้อเสีย [15]. แต่น่าเสียดายที่มันเป็นไปได้ว่านักชีววิทยาจบลงด้วยหลายdi? ต้นไม้ต่างกันอย่างใดอย่างหนึ่งและแท็กซ่า L ชุดเดียวกันเนื่องจากการ(i) มีข้อมูลหลายชุดที่มีอยู่ (ii) การอนุมานกับดิ? วิธีการต่างกันหรือ (iii) ซ้ำวิ่งของ nondeterministic เดียวกันวิธี. คำถามคือแล้ววิธีการใช้ประโยชน์จากสิ่งเหล่านี้อาจจะมีคุณภาพสูง แต่ di ต่างกัน? และต้นไม้ขัดแย้งส่วนหนึ่งข้างเปรียบเทียบด้วยตนเองและรวมพวกเขา เป็นไปได้วิธีการแก้ปัญหาคือการมองหาต้นไม้เดียวมากกว่า L ดีที่สุด "ที่เป็นตัวแทนของคอลเลกชันที. งานนี้ไม่น่ารำคาญเป็นที่รู้จักกันเป็นฉันทามติปัญหาต้นไม้ (CTP). ในมือข้างหนึ่งความหมายของ ดีที่สุด" ขึ้นอยู่กับที่ต้องการข้อมูลที่จะเก็บในต้นไม้ฉันทามติและบนมืออื่น ๆ ที่เป็นไปได้ฉันทามติต้นไม้ถูก จำกัด อย่างแท้จริงโดยระดับของความเข้มงวดของวิธีการที่นำมาใช้เช่นเดียวกับเมล็ดของต้นไม้ตัวชี้วัดที่ใช้เห็น[3] รูปที่ 1 แสดงให้เห็นถึงการแสดงแผนผังของกรณีนี้ โดยทั่วไปวิธีการที่เข้มงวดและเนื้อหยาบตัวชี้วัดที่ค่อนข้างนำไปสู่การแก้ไขได้ไม่ดีกับต้นไม้โหนดภายในไม่กี่ที่มีองศาสูงและเป็นส่วนสำคัญของข้อมูลที่มีอยู่ในต้นไม้การป้อนข้อมูลจะหายไป ในทางตรงกันข้ามเรามุ่งมั่นที่สืบมาแก้ไขอย่างเต็มที่ (ดังนั้น binary) ฉันทามติที่มีคุณภาพสูงต้นไม้สืบทอดข้อมูลมากที่สุดเท่าที่เป็นไปได้ ของเราวิธีการที่จะขึ้นดังนั้นการเพิ่มขึ้น speci ควัดทิศตะวันออกเฉียงเหนือเป็นเม็ดเล็กที่เรียกว่าคะแนนTreeRank. ในส่วนที่ 2 ที่เรารายงานก่อนหน้าเช่นเดียวกับงานที่เกี่ยวข้องและภาคตะวันออกเฉียงเหนือวัดTreeRank ฮี้ต้นไม้ที่มีความหมาย

ผลลัพธ์ (ไทย) 3:

1 . บทนำ
มติต้นไม้ปัญหาได้รับ  RST ที่อธิบายไว้ใน [ 1 ]
ข้างกับวิธีแก้ปัญหาวิธี มันมักปรากฏใน
โดเมนของไฟโลเจเนติก [ 13 ] แม้จะมีการใช้งานในการจัดกลุ่มโดเมนอื่น ๆเช่นกัน
.
phylogenetic ต้นไม้ประกอบด้วยโหนดและสาขา
( โค้ง ) และรูปแบบความสัมพันธ์เชิงวิวัฒนาการระหว่างชุดของวัตถุที่เกี่ยวข้องกับ L
เรียกว่า ซ่า .เหล่านี้เป็นข้อความและโหนดของต้นไม้และใบไม้

อาจจะสูญพันธุ์ภายในใกล้เคียงจุดเป็นตัวแทนของบรรพบุรุษ ในงานนี้เราจะ
พิจารณารากต้นไม้ไบนารีถ่วงน้ำหนัก คือมีอยู่ปมรากแตกต่างเดียว

เป็นบรรพบุรุษร่วมของทุกคนและ ความสัมพันธ์ที่แสดงโดยต้นไม้
ไม่ถ่วงน้ำหนักด้วยวิธีการใด ๆและแต่ละโหนดภายในเสมอ
ตรงสองโดยตรง เป็นต้น ปัญหาคือระบบเชื้อชาติ

สรุปว่ากลาง บรรพบุรุษ และสาขา ดังนั้น เพื่อให้ได้ความสัมพันธ์เชิงวิวัฒนาการให้ชนิดข้อมูลเช่น
จาก DNA หรือ RNA ลำดับ .
สำหรับวัตถุประสงค์นี้หลากหลายความคิดดี  erent อนุมาน
วิธีมีอยู่ แต่ละมีข้อดีและข้อเสียแต่ละ
[ 15 ]
ขออภัยมันเป็นโอกาสที่นักชีววิทยาลงเอยกับหลาย
ตี้  erent ต้นไม้หนึ่งและเดียวกันและการตั้งค่าฉันเนื่องจาก
( ฉัน ) มีข้อมูลหลายชุดพร้อมใช้งาน ( 2 ) อนุมานกับ
ตี้  erent วิธีการหรือ ( iii ) ซ้ำ วิ่ง ของ วิธี nondeterministic

เหมือนกัน คำถามคือ แล้ว การใช้ประโยชน์เหล่านี้อาจ
ที่มีคุณภาพสูง แต่ ดิ  erent และบางส่วนที่ขัดแย้งต้นไม้
ข้างด้วยตนเองเปรียบเทียบและผสานพวกเขา ทางออกที่เป็นไปได้
คือการมองหาต้นไม้เดียวมากกว่าผม N เป็นตัวแทนของคอลเลกชันที่ดีที่สุด "
T นี่ไม่ใช่เรื่องงานเรียกว่า
เอกฉันท์ต้นไม้ปัญหา ( CTP )
บนมือข้างหนึ่งความหมายของ " ดีที่สุดขึ้นอยู่กับที่ต้องการ
ข้อมูลรักษาในต้นไม้ร่วมกัน และในมืออื่น ๆจากต้นไม้

เป็นไปได้เป็นอักษร จำกัดโดยระดับความเข้มงวดของการใช้วิธีเช่นเดียวกับ
granularity ของต้นไม้เมตริกที่ใช้ดู [ 3 ] รูปที่ 1 แสดงการเป็นตัวแทน
แผนผังของสถานการณ์นี้ โดยทั่วไปวิธีการที่เข้มงวดและ

ทำให้ที่มีเนื้อหยาบเมตริกค่อนข้างไม่ดีแก้ไขต้นไม้น้อยภายในโหนดมี
องศาสูง และส่วนมากของข้อมูล
ที่มีอยู่ในใส่ต้นไม้จะหายไปในทางตรงกันข้าม เรามุ่ง
หลังการแก้ไขอย่างเต็มที่ ( ดังนั้น ไบนารีต้นไม้เอกฉันท์
คุณภาพสูงรับข้อมูลให้มากที่สุดเท่าที่จะเป็นไปได้ วิธีการของเรา
จึงเพิ่มมากขึ้นตามประเภท  C
 เน่เม็ดเล็กวัดที่เรียกว่าคะแนน treerank .
ส่วนที่ 2 ที่เรารายงานก่อนหน้านี้ รวมทั้งงานที่เกี่ยวข้องและ  เน่ที่ treerank
เดอวัด ความหมาย - ต้นไม้ข้างๆ